数据结构期末样卷（含答案）

精品

数据结构期末样卷

一． 单项选择题( 10分)

1．线性表逻辑顺序与存储顺序总是一致的，这种说法 A 。 A 正确 B 不正确

2. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行 。

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

3．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是___________。 A．e d c b a B．d e c b a C．d c e a b D．a b c d e

4．判定一个循环队列QU（最多元素为m0）为满队列的条件是 。 A．QU->front==QU->rear B．QU->front！==QU->rear

C．QU->front==（QU->rear+1）％m0 (不是很确定) D．QU->front!==（QU->rear+1）％m0

5．串是一种特殊的线性表，其特殊性体现在__________。 A．可以顺序存储 B.数据元素是一个字符 C．可以链接存储 D.数据元素可以是多个字符

6．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足_________。 A. 所有的结点均无左孩子 B. 所有的结点均无右孩子 C. 只有一个叶子结点 D. 是任意一棵二叉树

7．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点 。 A．正确 B．错误

8．广义表((a，b，c，d))的表头是 ，表尾是 。

A．a B．( ) C．(a，b，c，d) D．((a，b，c，d))

9．一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为 。 A．79，46，56，38，40，80 B. 84，79，56，38，40，46 C. 84，79，56，46，40，38 D. 84，56，79，40，46，38

10．用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变换情况如下：

（1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 则所采用的排序方法是 。

A. 选择排序 B. 希尔排序 C. 归并排序 D.快速排序

精品

二．填空题( 20分)

1．下面程序段的时间复杂度是 O(n2) 。 for (i=0;i

2．在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种物理存储单元上非连续、非顺序的存储结构 。

3．向栈中压入元素的操作是_先 移动栈顶指针 ，后 存入元素_ 。

4．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 1 。

5．在散列函数H（key）=key%p中，p应取 某个不大于哈希表表长m的数 。

6．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。

7．有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1），则A[8][5]的地址是 86 。

8. 采用邻接表存储的图，其广度优先遍历类似于二叉树的 按层遍历 。

9． 基数 排序不需要进行记录关键字间的比较。

10．一个有n个顶点的无向图最多有__ n*(n-1)/2 条边。

三．综合题( 50分)

1． 简述以下算法的功能（5分）。

Status A(LinkedList L) { //L是无表头结点的单链表

if ( L&&->next ) {

Q=L; L=L->next; P=L; While ( P->next ) P=P->next; P->next=Q; Q->next=NULL; }

return OK; } //A

//形成一个循环链表

2．简述以下算法的功能（5分）。 status algo2 (Stack S，int e) {

精品

Stack T； int d； InitStack (T)；

while ( !StackEmpty (S) ) ｛ Pop ( S，d)；

if (d!=e) Push (T，d )； }

while ( !StackEmpty (S) ) ｛

Pop ( T，d)； //这里应该有点问题 把S 改成T （我自己认为） Push ( S，d)； }

}

将堆栈S中的为e的值去掉。。（T充当临时存放的堆栈）

3．设给定权集w ={1，23，14，7，28，9}，试构造关于 w的一棵赫夫曼树，并求其加权路径长度 WPL。（10分）

4．请对下图的无向带权图，写出它的邻接表，并按克鲁斯卡尔/Prim算法求其最小生成树（10分）。

精品