数据复习题

《数据结构》试卷及答案 1．算法的目的是(    )。 A.找出数据结构的合理性          B.研究算法中输入和输出的关系  C.分析算法的效率以求改进        D.分析算法的易懂性和文档性 2．（    ）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号        B.数据对象        C.数据          D.数据结构 3．用链表表示线性表的优点是 (        )。 A.便于随机存取                  B.花费的存储空间比顺序表少  C.便于插入与删除                D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（  ）。 A.(A,B,C,D)        B. (D,C,B,A)      C. (A,C,D,B)    D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是(    )。 A.  front=maxSize                B.  (rear+1)%maxSize=front  C.  rear=maxSize                  D.  rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（  ）。 A. student          B. a good s        C. good        D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a85地址为（    ）。 A.23          B.33          C.18          D.  40 8．已知广义表    LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（  ）。 A. Gethead(Gethead(LS))            B. Gettail(Gethead(LS))  C. Gethead(Gethead(Gettail(LS)))    D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为(  ) 。 A.  CDBGFEA                    B.  CDBFGEA C.  CDBAGFE                    D.  BCDAGFE 10．下列存储形式中，(    ) 不是树的存储形式。 A.双亲表示法                    B.左子女右兄弟表示法 C.广义表表示法                  D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序是 ( )。 A.直接选择排序                    B.直接插入排序 C.快速排序                        D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（  ），且限于（  ）。 A.有序表  顺序存储结构            B.有序表  链式存储结构  C.随机表  顺序存储结构            D.随机表  链式存储结构 13．就平均查找速度而言，下列几种查找速度从慢至快的关系是（  ） A.顺序 折半 哈希 分块            B.顺序 分块 折半哈希  C.分块 折半 哈希 顺序            D.顺序 哈希 分块 折半 14．执行下面程序段时，执行S语句的次数为（  ） for(int I=1;I<=n;I++) for(int j=1;j<=I;j++) S; A.  n2      B.  n2/2      C.  n(n+1)      D.  n(n+1)/2 15．串是一种特殊的线性表，其特殊性体现在（ ） A.可以顺序存储              B.数据元素是一个字符  C.可以链接存储              D.数据元素可以是多个字符 16．树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论( )是正确的。 B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同  C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同  D.以上都不对 17．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为( )。 A. 60        B. 66        C. 67            D. 50 18．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( )个 A. 33        B. 34          C. 32            D. 30 19．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时，（ ）次比较后查找成功。 A.  1        B.  2        C.  4            D.  8 20．若有文件的关键字序列为：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]，以下为二路归并排序过程。第二趟为: A.[265 301] [129 751] [863 937] [694 742] [076 438]  B.[076 129 265 301 438 694 742 751 863 937]  C.[129 265 301 694 742 751 863 937] [076 438]  D.[129 265 301 751] [694 742 863 937] [076 438] 二、填空（本大题共6小题，每空2分，共12分；答案填在下表内） 1    算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 有穷性  、确定性 、可行性 、有零或多个输入和有一或多个输出。 2    算法优劣的五个标准是正确性、可使用性、健壮性、可读性，效力与低存储量需求。        3    有n个球队参加的足球联赛按主客场制进行比赛，共需进行n（n-1）_场比赛。 4    设有串t='I  am  a  student '，s='good'，那么Concat(t,s)= 'I am a student good'，Substr(t,8,7)= ‘student’__________。 5    在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个_队列结构，其主要特点是先进先出。    6    广义表((a),a)的表头是_______，表尾是_______。 三、判断题（对的打“√”，错的打“×”。每小题1分，共10分;答案填在下表内） 对1数据的逻辑结构与数据元素本身的内容和形式无关 。 错2 三个结点的二叉树和三个结点的树一样，都具有三种不同的形态。 对3中序序列和后序序列相同的二叉树为：空树和缺右子树的单支树 。 对4对于两棵具有相同关键字集合而形状不同的二叉排序树，中序遍历后得到的关键字排列顺序相同。 错5 序列{30，40，50，15，25，35，38，10}是堆 。 错6 对于无向图的生成树，从同一顶点出发所得的生成树相同 。 7 若设哈希表长m=14，哈希函数H(key)=key%11，表中已有4个结点。 addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是9。 8一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号则，则编号最小的叶子的序号是2k-2+1 ；编号是i的结点所在的层次号是「log2 i|+1。（「log2 i|表示向上取整」（根所在的层次号为1层）。 9在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。 10算法可以没有输入，但是必须有输出 。 四、画出树的孩子兄弟表示法示意的树或森林。（4分） 五、要求题（本大题共2小题，共12分） 设关键字的输入序列为{4，5，7，2，1，3，6} 1．（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。 2． （4分）上面的数据作为待排序的数据，写出用快速排序进行一趟划分后的数据序列 六、按要求做题（本大题共2小题，共12分） 1画出无向图G的邻接表存储结构，根据邻接表存储结构写出深度优先和广度优先遍历序列。（7分） 2 用prim算法求下图的最小生成树，写出最小生成树的生成过程。（5分） 七、算法分析题（本大题共5小题，共30分） 1．写出程序段的功能,并给出一个测试用例（一个输入数据和一个输出结果）(5分)。 void conversion() { Stack s; int n; SElemType e; initstack(s); printf("Please input number:"); scanf(“%d”,&n); while(n) {push(s,n%8); n=n/8; } while(!stackempty(s)) {pop(s,e); printf(“%d”,e); } } 2.下面是一个使用栈stack实现对二叉树进行非递归先根遍历的函数,请在标号处填写合适的语句。(每空1分，共5分) 程序: Void preorder(bitree *T) {bitree *stack[m]; int top; if(T!=NULL) {top=1; stack[top]=(1); while(  (2)  ) {p=stack[top]; top--; printf(“%d”,p->data); if(p->rchild!=NULL){ (3)  ;  stack[top]=p->rchild;} if(  (4) ) {  top++;  (5) ;} } } } ⑴                  ⑵                  ⑶                    ⑷                  ⑸ 3.请在标号处填写合适的语句。完成下列程序。(每空1分，共5分) int  Binary_Search(S_TBL  tbl，KEY  kx) {  /* 在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则，返回0  */ int  mid，flag=0； low=1；high=length；              while(    ⑴    &!flag )            {    /* 非空，进行比较测试 */ mid=   ⑵    ；          if(kxtbl.elem[mid].key)    ⑷    ；  else  { flag=  ⑸  ；break；}  } return  flag; } ⑴                  ⑵                  ⑶                    ⑷                  ⑸ 4.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写合适的语句。(每空1分，共5分) 程序： Void seletesort(int A[n],int n) { int i,j,t,minval,minidx; for(i=1;i<=n-1;i++) {  minval=A[i+1]; (1) for(j=i+2;j<=n;j++) if(  (2)  ) {  (3)  ;  minidx=j;} if(  (4)  )  {t=A[i+1]; (5) A[minidx]=t; } } } ⑴                  ⑵                  ⑶                    ⑷                  ⑸ 5 试写出求有向无环图的关键路径算法的设计思路（10分） 数据结构试卷A答案 选择题（本大题共20小题，每题1分，共20分；答案填在下表内） 1 2 3 4 5 6 7 8 9 10 C B : C : D : B : D : B : C : A : C 11 12 13 14 15 16 17 18 19 20 : C A : B : D : B : A : C : A C D                     二、填空题（本大题共5小题，每空1分，共12分；答案填在下表内） 1        有穷性        确定性          可行性 2        可读性        健壮性            效率 3        n(n-1) 4        'student' 5        队列        先进先出 6        (a)          (a) 三、判断题（对的打“√”，错的打“×”。每小题1分，共10分） 1）true ;  2）flase;  3）true;  4）true;  5）flase; 6）flase ;  7）true;  8）true;  9）flase;  10）true 四、画出树的孩子兄弟表示法示意的树或森林。（4分） 其他形式的树形结构酌情给分。 五、要求题（本大题共2小题，共12分） 1. 2. 一趟划分后的数据序列 3 1 2 4 7 5 6 六、按要求做题（12分） 1 DFS遍历序列v1 v2 v4 v8 v5 v3 v6 v7(或1 2 4 8 5 3 6 7) BFS遍历序列v1 v2 v3 v4 v5  v6 v7 v8(或1 2 3 4 5  6 7 8) 邻接点的顺序可以不同，可以有不同的深度优先和广度优先遍历序列。（5分，如有错误酌情扣分。） 2 50 40 50 30 50 40 50 40 50 七、算法设计题（30分） 1.将十进制转化成八进制数（5分） 测试用例：输入10 输出12 2（5分，每空1分）（1）T (2) top>0 (3) top++ (4) p->lchild!=NULL (5) stack[top]=p->lchild 3 （5分，每空1分） （1）low<=high (2) (low+high)/2 (3) high=mid-1 (4) low=mid+1 (5) 1 4. （5分，每空1分） （1）minidx=i+1 (2) minval>A[j] (3) minval=A[j] (4) i!=j (5) A[i+1]=A[minidx] 5（10分，不同答案，酌情得分） 输入顶点和弧信息，建立其邻接表 计算每个顶点的入度 对其进行拓扑排序 排序过程中求顶点的Ve[i] 将得到的拓扑序列进栈 按逆拓扑序列求顶点的Vl[i] 计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动 第 2 学期 数据结构试卷A 选择题（本大题共15小题，每题2分，共30分；答案填在下表内） 1.从一个长度为100的顺序表中删除第30个元素时需向前移动      个元素 A、70      B、71    C、69    D、30 2.在一个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为______。 A、 top不变    B、top=0        C、top=top-1  D、top=top+1 3.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功情况下,则平均比较____个结点。 A、n    B、n/2    C、(n-1)/2    D、(n+1)/2 4.在一个单链表中,若要删除p指针所指结点的后继结点,则执行 A、p-> next; p-> next=p-> next-> next; B、p-> next=p-> next-> next; C、p=p-> next; D、p=p-> next->>next; 5.在一个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行___。 A、front-> next=s；    front=s； B、s-> next=rear;      rear=s； C、rear-> next=s;      rear=s； D、s-> next=front;      front=s； 6.在一棵度为3的树中度为3的结点数为3个,度为2的结点数为1个,度为1的结点数为1个,那么度为0的结点数为____个 A、6    B、7  C、 8    D、9 7.假定一棵二叉树的结点数为33个,则它的最小高度为__,最大高度为___ A、 4,33  B、5,33  C、6,33 D、6,32 8. 在一棵完全二叉树中,若编号为i的结点有右孩子,则该结点的右孩子编号为___。 A、2i  B、2i+1  C、2i-1  D、i/2 9.在一个有向图中,所有顶点的入度之和等于所有弧数和___倍。 A、1     B、2    C、3    D、4 10.对于一个具有N个顶点的图,若用邻接矩阵表示,则该矩阵的大小为___。 A、  N      B、(N-1)2  C、(N+1)2  D、  N2 11.已知一个图如图所示，在该图的最小生成树中各边上数值之和为____。 A、21    B、26      C、28        D、33  12.已知一个图如图所示，由该图行到的一种拓朴序列为      A、v1  v4  v6  v2  v5  v3  B、v1  v2  v3  v4  v5  v6  C、v1  v4  v2  v3  v6  v5  D、v1  v2  v4  v6  v3  v5 13.二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[2][4]的起始地址与M按列存储时元素  的起始地址相同。 A、m[2][4]  B、M[4][2]  C、M[3][1]  D、M[1][3] 14.具有6个结点的无向图至少应有     条边才能保证是连通图。 A .  5   B、 6    C、  7    D、  8    15.采用邻接表存储的图的深度优先遍历类似于二叉树的        。 A  先序遍历B中序遍历  C.  后序遍历  D. 按层遍历  二、填空题（本大题共5小题，每空1分，共8分；答案填在下表内） 1 2 3 4 5 6 7 8                                 1.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、树形结构和图型结构。 2.评价算法的标准很多，通常是以执行算法所需要的时间和所占用的空间来判别一个算法的优劣。 3.线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的位置也是相邻的。 4.空格串的长度为串中所包含空格字符的个数，空串的长度为 零。 5.加上表示指向前驱和后继 的线索的二叉数称为线索二叉树。 三、判断题（对的打“√”，错的打“×”。每小题1分，共10分） （ ×）1.线性表的唯一存储形式是链表。 （ √）2.已知指针P指向键表L中的某结点，执行语句P=P-〉next不会删除该链表中的结点。 （ √）3.在链队列中，即使不设置尾指针也能进行入队操作。 （ ×）4.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。 （× ）5.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。 （√ ）6.快速排序是不稳定排序。 （ × ）7.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最短的一条。 （ × ）8.若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。 （ × ）9.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。 （× ）10.基数排序是多关键字排序。从最低位关键字起进行排序。 四、应用题。（共44分） 1.画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS和BFS(广度优先遍历）序列。（12分） 2.假设用于通信的电子由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}画出哈夫曼树，并为这8个字母设计哈夫曼编码。（8分） 3. 已知序列{70，73，69，23，93，18,11，68}请给出直接插入排序作升序排序每一趟的结果和快速排序作升序排序时一趟的结果。（10分） 4.设有一组关键字关键码集为 {47，7，29，11，16，92，22，8，3}，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL。（8分） 5. 二叉树的先序遍历序列为  A B C D E F G H I，中序遍历序列为  B C A E D G H F I，画出这棵二叉树。(6分) 五、算法设计题（8分） 定义有序表抽象数据类型，并据此类型设计折半查找算法。 2学期数据结构试卷A 参考答案及评分标准 一、 选择题本大题共15小题，每题2分，共30分 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A D D B C C C B A D B A D A A                               二、 填空题（本大题共5小题，每空1分，共8分） 1 2 3 4 5 6 7 8 树型结构 图型结构 时间 空间 位置 空格 零 后继                 三、判断题（每小题1分，共10分） 1 2 3 4 5 6 7 8 9 10 × √ √ × × √ × × × ×                     应用题44分） 1.（12分） 011000 101000 100001 010010 000101 001010 ∧ 2 1 0 A   ∧ 3 0 1 B   0 2 0 C 5 1 3 D 4 3 ∧ 5 4 E   2 ∧ 4 5 F       DFS序列:ABDEFC BFS序列:ABCDFE 2. （8分） 7 19 2 6 32 3 21 10 0010 10 00000 0001 01 00001 11 011                 3. （10分）直接插入排序 70，73，69，23，93，18,11，68 [70，73]，69，23，93，18,11，68 [70，69，73]， 23，93，18,11，68 [23,70，69，73]， 93，18,11，68 [23,70，69，73， 93]，18,11，68 [18,23,70，69，73， 93]， 11，68 [11，18,23,70，69，73， 93]， 68 [11，18,23,68,70，69，73， 93] 快速排序 [68,11,69,23,18] ,70,[93,73] 4. （8分） 0  1  2  3  4  5  6  7  8  9  10 11 22   47 92 16 3 7 29 8                       ASL=5/3 5. （6分） 算法设计题（8分） typedef struct {  int key; float info; }JD; int binsrch(JD r[],int n,int k) {  int low,high,mid,found; low=1;  high=n; found=0; while((low<=high)&&(found==0)) {  mid=(low+high)/2; if(k>r[mid].key)  low=mid+1; else if(k==r[mid].key)  found=1; else  high=mid-1; } if(found==1) return(mid); else return(0); }