青岛理工大学成人教育期末考试 数据结构复习题2

教师试做时间出题教师房斐斐取题时间

审核教研室主任

出题单位使用班级考试日期

考试成绩期望值印刷份数规定完成时间交教学部印刷日期

学号：姓名：班级：

.............................密...........................封.............................线.............................

专业年级班20—~20—学年第一学期数据结构课试卷试卷类型：复习题2卷

六

题号一二三四五七八九+总成绩

得分

一、填空题(每空1分，共10分)

1.数据结构被形式地定义为(D,R),其中D是——的有限集合，R是D上的——有限集合。

2.栈中元素的进出原则是o

3.假设有二维数组A6X8,每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置(基地址)为1000,则末尾元素

心的第一个字节地址为；若按行存储时，元素A”的第一个字节地址为o

4.一棵具有257个结点的完全二叉树，它的深度为o

5.〃个顶点e条边的图，若采用邻接表存储，则空间复杂度为。

6.线性有序表(a］，a2,a3,azQ是从小到大排列的，对一个给定的值h用二分法检索表中与左相等的元素，在查找不成功的情况下，

最多需要检索次。

7.设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是

8.在堆排序、快速排序和归并排序中，若只从最坏情况下最快并且要节省内存考虑，则应选取方法。

二、选择题(每题2分，共30分)

()1.算法分析的两个主要方面是：

(A)空间复杂性和时间复杂性(B)正确性和简明性

(C)可读性和文档性(D)数据复杂性和程序复杂性

()2.在n个结点的顺序表中，算法的时间复杂度是0(1)的操作是：

(A)访问第i个结点(IWiWn)和求第i个结点的直接前驱(2WiWn)

(B)在第i个结点后插入一个新结点(IWiWn)

(C)删除第i个结点(IWiWn)

(D)将n个结点从小到大排序

()3.双向循环链表的每个结点中包括两个指针next和previous,分别指向该结点的后继和前驱结点。现要删除指针p所指向的结

点，下面的操作序列中哪一个是正确的？

(A)p-next-)previous=p->previous;p->previous->next=p->next；

(B)p-〉next-〉previous=p->next;p->previous-)next=p->previous；

(C)p->previous-〉next=p->previous;p->next-〉previous=p->next；

(D)p->previous-〉next-)next=p-next;p->next-〉previous=p->previous；

()4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址：

(A)必须是连续的(B)部分地址必须是连续的

(C)一定是不连续的(D)连续或不连续都可以

()5.若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为pl,p2,p3,…，pn,若pl=n,则pi为

(A)i(B)n=i(C)n-i+1(D)不确定

()6.数组Q［n］用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n,计

算队列中元素的公式为

(A)r—f(B)(n+f—r)%n(C)n+r—f(D)(n+r—f)%n

()7.判定一个栈ST(最多元素为m)为空的条件是

(A)ST->topOO(B)ST->top=0(C)ST->topOm(D)ST->top=m

青岛理工大学成教学院试卷纸共页第1页

试题要求：1、试题后标注本题得分；2、试卷应附有评卷用标准答案，并有每题每步得分标准；3、试卷必须装订，拆散无效；4、试卷必

须打印或用碳素笔楷书，以便誉印；5、考试前到指定地点领取试卷；6、各题之间应适当给学生留下答题的空间。

学号;姓名:班级:

密.............................封...............................线

()8.判定一个队列QU(最多元素为m)为满队列的条件是

(A)QU->rear—QU->front==m(B)QU->rear—QU->front—1==m

(C)QU->front==QU->rear(D)QU->front==QU->rear+l

)9.设串si='ABCDEFG',S2='PQRST',函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i开

始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(si,2,len(S2)),subs(si,len(S2),2))的结果串是:

(A)BCDEF(B)BCDEFG(C)BCPQRST(D)BCDEFEF

()10.具有12个结点的完全二叉树有个度为2的结点。

0111101

(A)4(B)5(06(D)7

1001001

()11.具有n(n>0)个结点的完全二叉树的深度为.

1000100

(A)Flog2(n)l(B)Llog2(n)J(C)Llog2(n)J+l(D)「log2(n)+11

1100110

()12.已知图的邻接矩阵如右图，根据算法，则从顶点0出发，按深度优先遍历的结点序1011010

列是：0001101

(A)0243156(B)0135642I100010

(C)0423165(D)0134256

()13.设哈希表长度为11,哈希函数为H(key)=keymod11。表中己有4个元素H(15)=4；H(38)=5；

H(61)=6；H(84)=7其余地址为空，若用二次探测再散列处理冲突，关键字为49的元素的地址是.

(A)3(B)5(08(D)9

()14.假设有60行70列的二维数组60,1...70］以列序为主序顺序存储，其基地址为10000,每个元素占2个

存储单元，那么第32行第58列的元素a［32,58］的存储地址为。(无第0行第0列元素)

(A)16902(B)16904(C)14454(D)答案A,B,C均不对

()15.广度优先遍历类似于二叉树的

(A)先序遍历(B)中序遍历(C〉后序遍历(D)层次遍历

三、判断题(每题1分，共10分)

()1.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

()2.线性表在物理存储空间中也一定是连续的。

()3.顺序存储方式只能用于存储线性结构。

()4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

()5.若二叉树用二叉链表作存贮结构，则在"个结点的二叉树链表中只有个非空指针域。

()6.二叉树中每个结点的两棵子树是有序的。

()7.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值，且小于其右非空子树(若

存在的话)所有结点的关键字值。

()8.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

()9.用二叉链表法(link-rlink)存储包含〃个结点的二叉树，结点的2〃个指针区域中有〃+1个为空指针。

()10.设有一稠密图G,则G采用邻接矩阵存储较省空间。

四、简答题(共18分)

1.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？(4分)

2.把如图所示的树转化成二叉树，并写出其前序、中序、后序遍历序列。(6分)

3.假定用于通信的电文仅由8个字母cl,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频率分别为5,25,

3,6,10,11,36,4.(共8分)

(1)试构造哈夫曼树(4分)

(2)试为这8个字母设计不等长Huffman编码，(2分)

(3)求其WPL值。(2分)

青岛理工大学成教学院试卷纸

学号;姓名:班级:

线.............................

五、算法理解题(共16分)

1.阅读算法，写出该算法的结果(5分)

main()

{SqStackTpsq;inti;charch;

InitStack(&sq);

For(ch='A';chv='A'+6;ch++)

{Push(&sq,ch);printf("%c”,ch);

}

while(!EmptyStack(sq))

{Pop(&sq,&ch);

printf("&c",ch);

}prints%")；

)

2.阅读算法，写出该算法的功能(5分)

Statusex331()

(

InitStack(S);InitQueue(Q);

scanf(ch);

while(ch!=0@0){

Push(S,ch);EnQueue(Q,ch);

scanf(ch);

)

state=TRUE;

while(!StackEmpty&&state)

{

if(GetTop(S)==GetHead(Q))

{Pop(S);DeQueue(Q);}

elsestate=FALSE;

returnstate;