《数据结构》试卷B

一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。每小题2分，共30分) 1.计算机中算法是指( )。

A.计算方法 B.排序方法 C.解决某一问题的有限运算序列 D.调度方法

2.在一个单链表中，若指针p所指结点不是最后结点，在p之后插入指针s所指结点，则应执行的语句序列为( )。

A. s->next=p；p->next=s; B. s->next=p->next;p->next=s； C. s->next=p->next;p:=s; D. p->next=s;s->next=p;

3. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）

A．head==NULL B．head->next==NULL C．head->next==head D．head!=NULL

4.循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是( )。 A.(rear-front+m) MOD m B.rear-front+1 C.rear-front-1 D.rear-front

5. 从邻接矩阵A＝可以看出，此图共有（1）个顶点。如果是有向图，该图共有（2）条弧；

（1） A、9 B、3 C、6 D、1

（2） A、5

B、4

C、3

D、2

6. 中缀表达式A-(B+C/D)*E的后缀形式是 ( ) A、AB-C+D/E* B、ABC+D/-E* 7. 下列程序段的算法复杂度为（）

I=0; s=0; while(s

1

C、ABCD/E*+- D、ABCD/+E*-

A、O（n）B、 O（n） C、（n） D、O（㏒2n） 8. 下面哪一方法可以判断出一个有向图是否有环（回路）：

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 9.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为( )

A.n B.n+1 C.n-1 D.n+边数

10.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。 A.n B.n+1 C.n-1 D.n/2 11. 在有向图中每个顶点的度等于该顶点的（ ）。

A. 入度与出度之和 C. 入度

B. 出度

2

D. 入度与出度之差

12. 输入序列为（A，B，C，D），顺序通过一个栈后，不可能得到的输出序列有( )

A、（A，B，C，D） B、（D，C，B，A） C、（A，C，D，B） D、（C，A，B，D） 13. 无向图的邻接矩阵是一个( )

A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵

14. 一个向量的第一个元素的存储位址为100，每个元素的长度为2个字节，则第5 个元素的起始位址为（）

A、110 B、108 C、100 D112

15. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A．求子串 B．联接 C．匹配 D．求串长

二、判断题(判断下列各题，正确的在题干后面括号内打“√”，错误的打“×”。

每小题1分，共10分)

1、（ ）二叉树是一种特殊结构的树。

2、（ ）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

3、（ ）具有n个顶点的完全有向图有n*(n-1)/2 条边。

2

4、（ ）希尔排序是一种稳定的排序方法。

5、（ ）折半查找只适用于有序表，包括有序的顺序表和有序的链表。 6、（ ）已知一棵叉树的先序序列和中序序列一定能构造出该二树。 7、（ ）在用单链表表示的链式队列时，队头在链表的链尾位置。

8、（ ）算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。

9、（ ）n个结点的完全二叉树的高度为┖log2n┘+1。 10、

（ ）进行折半搜索的表必须是顺序存储的有序表。

三、填空题(每小题2分，共10分)

1、在带有头结点的单链表L中，第一个点元素的指针是＿＿＿＿＿＿。 2、在双循环表中，在指针p所指结点前插入指针s所指结点，需执行下列四个语句：

s->next=p; s->prior=p->prior; p->prior=s; ＿＿＿＿＿＿＿＿；

3、已知一棵二叉树的叶子结点数为50，一分枝结点数为30，则总结点数为＿＿＿＿。

4、深度为K的完全二叉树至少有_________个结点，至多有_________个结点。 5、 图的主要存储结构有两种，分别为：_________和_________。 四、应用题(每小题6分，共30分)

1. 对下图所示二叉树分别按前序﹑中序﹑后序遍历，给出相应的结点序列。 b e g a c

df

h 2.有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为8、14、10、4、18，请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)，求出每个字符的哈夫曼编码。

3

3. 下图是用邻接表存储的图，画出此图，并写出从C点开始按深度优先遍历该图的结果。（6分）

4. 将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉排序树中，画出插入关键码后的二叉排序树。（6分）

5. 已知一组关键字集合为{240，29，345，189，100，20，21，35，3，208，78，99，45，350}共14个元素，散列函数为H（k）= k mod 13，采用拉链法处理冲突，试设计这种链表结构，并求出在等概率下查找成功的平均查找长度。 五、算法填空题(每空2分,共10分)

1、下列算法是在带头结点的链表L的第i个结点前插入一个值为e的结点，成功插入，返回1，否则返回0。请填空，使之完整。 typedef struct node {int data; Struct node *next; }Lnode,*Linklist;

Int insert(Linklist &L, int I ,int e) { Int j; Linklist p,s; P=L->next;

4

______①______;

While(p&&jnext;} If(p){s=(Linklist)malloc(sizeof(Lnode)); s->data=e;

_____②___________ ; p->next=s; return 1; } Else

{printf(“error”); ____③_________; } }

2、下面算法的功能是在循环队列Q中删除一个元素，并由e返回。请填空使之完整。

#define MAXSIZE 100 typedef struct {int elem[MAXSIZE]; Int front,rear; Int len; }sqlist;

Void dequeue(sqlist &Q,int &e)

{if(Q.len==0){printf(“队空\\n”); return ;} e=______④________;

q.front=(q.front+1)%MAXSIZE; Q.len--;

If(____⑤______)q.front=q.rear=-1; }

5

六、设计题(共10分)

编写函数:将带头结点的链表L的第i个结点删除，如果删除成功，则返回1，否则返回0。 (要求必须有结构定义，结点包含数据域data和指针域next)

6