数据结构试卷及答案

《数据结构》试卷及答案1．算法分析的目的是(C)。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2．（B）是具有相同特性数据元素的集合，是数据的子集。A.数据符号B.数据对象C.数据D.数据结构3．用链表表示线性表的优点是(C)。A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同4．输入序列为（A,B,C,D）不可能的输出有（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为数组的最大长度，队满的条件是(B)。A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeD.rear=front6．设有串t='Iamagoodstudent'，那么Substr(t,6,6)=（D）。A.studentB.agoodsC.goodD.agood7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（B）。A.23B.33C.18D.408．已知广义表 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.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE10．下列存储形式中，()不是树的存储形式。A.双亲表示法B.左子女右兄弟表示法C.广义表表示法D.顺序表示法11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是()。A.直接选择排序B.直接插入排序C.快速排序D.起泡排序12．采用折半查找方法进行查找，数据文件应为（），且限于（）。A.有序表顺序存储结构B.有序表链式存储结构C.随机表顺序存储结构D.随机表链式存储结构13．就平均查找速度而言，下列几种查找速度从慢至快的关系是（）A.顺序折半哈希分块B.顺序分块折半哈希C.分块折半哈希顺序D.顺序哈希分块折半14．执行下面程序段时，执行S语句的次数为（）for(intI=1;I<=n;I++)for(intj=1;j<=I;j++)S;A.n2B.n2/2C.n(n+1)D.n(n+1)/215．串是一种特殊的线性表，其特殊性体现在（）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符16．树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论()是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对17．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为()。A.60B.66C.67D.5018．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有()个A.33B.34C.32D.3019．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时，（）次比较后查找成功。A.1B.2C.4D.820．若有文件的关键字序列为：[265][301][751][129][937][863][742][694][076][438]，以下为二路归并排序过程。第二趟为:A.[265301][129751][863937][694742][076438]B.[076129265301438694742751863937]C.[129265301694742751863937][076438]D.[129265301751][694742863937][076438]二、填空题（本大题共6小题，每空2分，共12分；答案填在下表内） 1 算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是有穷性、_确定性_、_可行性_、有零或多个输入和有一或多个输出。 2 算法优劣的五个标准是正确性、可使用性、_可读性_、_健壮性_、_效率_。 3 有n个球队参加的足球联赛按主客场制进行比赛，共需进行__n(n-i)_场比赛。4 设有串t='Iamastudent'，s='good'，那么Concat(t,s)='Iamastudentgood'，Substr(t,8,7)=_’student’_。 5 在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个_队列_结构，其主要特点是__先进先出___。 6 广义表((a),a)的表头是_（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)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是9。√8一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号则，则编号最小的叶子的序号是2k-2+1；编号是i的结点所在的层次号是「log2i|+1。（「log2i|表示向上取整」（根所在的层次号规定为1层）。×9在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。√10算法可以没有输入，但是必须有输出。四、画出树的孩子兄弟表示法示意的树或森林。（4分）EG∧∧I∧∧A∧B∧∧CD∧H∧∧FEG∧∧I∧∧A∧B∧∧CD∧H∧∧FAA

B

C

D

E

F

G

H

I

五、要求题（本大题共2小题，共12分）设关键字的输入序列为{4，5，7，2，1，3，6}1．（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。4

4

5

7

4

5

7

4

5

7

2

1

4

2

5

7

1

2

5

6

1

4

3

3

2

4

5

1

7

3

2

4

5

1

7

6

3

2

4

6

1

7

5

2.一趟划分后的数据序列3124756六、按要求做题（本大题共2小题，共12分）1画出无向图G的邻接表存储结构，根据邻接表存储结构写出深度优先和广度优先遍历序列。（7分）V1

V8

V7

V6

V5

V4

V3

V2

V1

V8

V7

V6

V5

V4

V3

V2

DFS遍历序列v1v2v4v8v5v3v6v7(或12485367)BFS遍历序列v1v2v3v4v5v6v7v8(或12345678)邻接点的顺序可以不同，可以有不同的深度优先和广度优先遍历序列。（5分，如有错误酌情扣分。）2用prim算法求下图的最小生成树，写出最小生成树的生成过程。（5分）4542526550603070504050V5

V7

V4

V4

V3

V1

V3

V3

V1

V5

V6

V1

V7

V2

V2

V7

4542526550603070504050V5

V7

V4

V4

V3

V1

V3

V3

V1

V5

V6

V1

V7

V2

V2

V7

V2

V4

V5

V6

V6

七、算法分析设计题（本大题共5小题，共30分）1．写出程序段的功能,并给出一个测试用例（一个输入数据和一个输出结果）(5分)。voidconversion(){Stacks;intn;SElemTypee;initstack(s);printf("Pleaseinputnumber:");scanf(“%d”,&n);while(n){push(s,n%8);n=n/8;}while(!stackempty(s)){pop(s,e);printf(“%d”,e);}}1.将十进制转化成八进制数（5分）测试用例：输入10输出122.下面是一个使用栈stack实现对二叉树进行非递归先根遍历的函数,请在标号处填写合适的语句。(每空1分，共5分)程序:Voidpreorder(bitree*T){bitree*stack[m];inttop;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);}

}}}⑴⑵⑶⑷⑸（1）T(2)top>0(3)top++(4)p->lchild!=NULL(5)stack[top]=p->lchild3.请在标号处填写合适的语句。完成下列程序。(每空1分，共5分)intBinary_Search(S_TBLtbl，KEYkx){ intmid，flag=0；low=1；high=length；while(⑴&!flag){/*非空，进行比较测试*/mid=⑵；if(kx<tbl.elem[mid].key) ⑶；else if(kx>tbl.elem[mid].key)⑷；else{flag=⑸；break；}}returnflag;}⑴⑵⑶⑷⑸（1）low<=high(2)(low+high)/2(3)high=mid-1(4)low=mid+1(5)14.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写合适的语句。(每空1分，共5分)程序：Voidseletesort(intA[n],intn){inti,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;}

}}⑴⑵⑶⑷⑸（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]的关键活动数据结构试卷A答案选择题（本大题共20小题，每题1分，共20分；答案填在下表内）12345678910CB:C:D:B:D:B:C:A:C11121314151617181920:CA:B:D:B:A:C:ACD二、填空题（本大题共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分）AA

B

C

D

E

F

G

H

I

其他形式的树形结构酌情给分。五、要求题（本大题共2小题，共12分）4

4

5

7

4

5

7

4

5

7

2

1

4

2

5

7

1

2

5

6

1

4

3

3

2

4

5

1

7

3

2

4

5

1

7

6

3

2

4

6

1

7

5

2.一趟划分后的数据序列3124756六、按要求做题（12分）1DFS遍历序列v1v2v4v8v5v3v6v7(或12485367)BFS遍历序列v1v2v3v4v5v6v7v8(或12345678)邻接点的顺序可以不同，可以有不同的深度优先和广度优先遍历序列。（5分，如有错误酌情扣分。）2V6

V6

504050405030504050V4

V4

V7

V2

V3

V1

V3

V1

V3

V5

V1

V7

V2

V6

V6

504050405030504050V4

V4

V7

V2

V3

V1

V3

V1

V3

V5

V1

V7

V2

V6

V5

V2

V7

V4

V5

V5

V4

V1

V7

V2

V5

V6

V3

V1

V5

V4

V1

V7

V2

V5

V6

V3

V1

V3

V4

V2

V7

V6

七、算法设计题（30分）1.将十进制转化成八进制数（5分）测试用例：输入10输出122（5分，每空1分）（1）T(2)top>0(3)top++(4)p->lchild!=NULL(5)stack[top]=p->lchild3（5分，每空1分）（1）low<=high(2)(low+high)/2(3)high=mid-1(4)low=mid+1(5)14.（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、70B、71C、69D、302.在一个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为______。A、top不变B、top=0C、top=top-1D、top=top+13.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功情况下,则平均比较____个结点。A、nB、n/2C、(n-1)/2D、(n+1)/24.在一个单链表中,若要删除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、6B、7C、8D、97.假定一棵二叉树的结点数为33个,则它的最小高度为__,最大高度为___A、4,33B、5,33C、6,33D、6,328.在一棵完全二叉树中,若编号为i的结点有右孩子,则该结点的右孩子编号为___。A、2iB、2i+1C、2i-1D、i/29.在一个有向图中,所有顶点的入度之和等于所有弧数和___倍。A、1B、2C、3D、410.对于一个具有N个顶点的图,若用邻接矩阵表示,则该矩阵的大小为___。A、NB、(N-1)2C、(N+1)2D、N211.已知一个图如图所示，在该图的最小生成树中各边上数值之和为____。A、21B、26C、28D、3312.已知一个图如图所示，由该图行到的一种拓朴序列为A、v1v4v6v2v5v3B、v1v2v3v4v5v6C、v1v4v2v3v6v5D、v1v2v4v6v3v513.二维数组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[3][1]14.具有6个结点的无向图至少应有条边才能保证是连通图。5B、6C、7D、815.采用邻接表存储的图的深度优先遍历类似于二叉树的。A先序遍历B中序遍历C.后序遍历D.按层遍历二、填空题（本大题共5小题，每空1分，共8分；答案填在下表内）123456781.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、（1）树形结构和（2）图形结构。2.评价算法的标准很多，通常是以执行算法所需要的（3）时间和所占用的（4）空间来判别一个算法的优劣。3.线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的（5）位置也是相邻的。4.空格串的长度为串中所包含（6）空格字符的个数，空串的长度为（7）零5.加上表示指向前驱和（8）后继的线索的二叉数称为线索二叉树。三、判断题（对的打“√”，错的打“×”。每小题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分）011000101000100001010010000101001010012∧A012∧10∧3B10∧3020C0205531D314443∧5E43∧552∧4F52∧4DFS序列:ABDEFCBFS序列:ABCDFE2.假设用于通信的电子由字符集{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分）7192632321100010100000000010100001110113.已知序列{70，73，69，23，93，18,11，68}请给出直接插入排序作升序排序每一趟的结果和快速排序作升序排序时一趟的结果。（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.设有一组关键字关键码集为{47，7，29，11，16，92，22，8，3}，哈希表表长为11，Hash(key)=keymod11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL。（8分）012345678910112247921637298A

H

B

C

F

D

E

G

I

5.二叉树的先序遍历序列为ABCDEFGHI，中序遍历序列为A

H

B

C

F

D

E

G

I

五、算法设计题（8分）定义有序表抽象数据类型，并据此类型设计折半查找算法。算法设计题（8分）typedefstruct{intkey;floatinfo;}JD;intbinsrch(JDr[],intn,intk){intlow,high,mid,found;low=1;high=n;found=0;while((low<=high)&&(found==0)){mid=