安徽大学数据结构期末试卷2006-2007第1学期数据结构与算法试卷(A卷)

（时间120分钟）

院/系 专业 姓名 学号

题 号 得

一 二 三 四 五 六 七 总分 分 一、选择题（每小题1.5分，共15分）

得(请在下面的四个选项中选择一个正确选项，并将其序号填入空 格内。)

分 1、某双向链表中的结点如下图所示，删除t所指结点的操作为 。

t prior

… …

data … …

next

(第一题，第1小题图)

A. t->prior->next=t->next； t->next->prior=t->prior B. t->prior->prior=t->prior； t->next->next=t->next C. t->prior->next=t->prior； t->next->prior=t->next D. t->prior->prior=t->next； t->next->prior=t->prior

2、循环链表的主要优点是 。

A. 不再需要头指针了

B. 已知某个结点的位置后，能很容易找到它的直接前驱结点 C. 在进行删除操作后，能保证链表不断开 D. 从表中任一结点出发都能遍历整个链表

3、在链表结构中，采用 可以用最少的空间代价和最高的时间效率实现队列结构。

A. 仅设置尾指针的单向循环链表 B. 仅设置头指针的单向循环链表 C. 仅设置尾指针的双向链表 D. 仅设置头指针的双向链表

《 数据结构与算法 》试卷 第 1 页 共 8 页

4、若需将一个栈S中的元素逆置，则以下处理方式中正确的是 。

A. 将栈S中元素依次出栈并入栈T，然后栈T中元素依次出栈并进入栈S B. 将栈S中元素依次出栈并入队，然后使该队列元素依次出队并进入栈S C. 直接交换栈顶元素和栈底元素 D. 直接交换栈顶指针和栈底指针

5、下面关于串的的叙述中，哪一个是不正确的 。

A. B. C. D.

串是字符的有限序列 空串是由空格构成的串

模式匹配是串的一种重要运算

串既可采用顺序存储，也可采用链式存储

6、若某二叉树的先序遍历序列和中序遍历序列分别为PBECD、BEPCD，则该二叉树的后序遍历序列为 。

A. PBCDE B. DCEBP C. EBDCP D. EBPDC

7、对于具有n个元素的有序序列进行二分查找时， 。

A. 查找元素所需的比较次数与元素的位置无关

B. 查找序列中任何一个元素所需要的比较次数不超过log2(n1) C. 元素位置越靠近序列后端，查找该元素所需的比较次数越少 D. 元素位置越靠近序列前端，查找该元素所需的比较次数越少

8、以下序列中 不符合堆的定义。

A. B. C. D.

(4,10,15,72,39,23,18) (58,27,36,12,8,23,9) (4,10,18,72,39,23,15) (58,36,27,12,8,23,9)

9、对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用 。

A. 希尔排序 B.直接插入排序

C.快速排序 D.堆排序

10、设有一个用线性探测法解决冲突得到的散列表(或哈希表)如下图所示，散列函数为H(k)=k % 11，若要查找元素14，探查的次数为 。

0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 (第一题，第10小题图)

A.4 B.9 C.3 D.6

《 数据结构与算法 》试卷 第 2 页 共 8 页

二、填空题（每小题1.5分，共15分） (请将正确的结果填入空格内。)

得分 1、一个“好”的算法要考虑以下标准：正确性 、可读性 、 和高效率与低存储量需求。 2、对于二维数组a[0..4,0..5]，设每个元素占1个存储单元，且以行为主序存储，则元素a[2,4]相对于数组空间起始地址的偏移量是 。

3、两个串相等的条件是 。 4、由权值为9,2,5,7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为 。

5、一棵二叉树如下图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1，若某结点的下标为i,则其左孩子位于下标2i处、右孩子位于下标2i+1处)，则该数组的大小至少为(含数组的0单元，但不存储) 。

6、一棵二叉树如下图所示，若采用二叉链表存储该二叉树(各个结点包括结点的数据、左孩子指针、右孩子指针)，则该链表中空指针的数目为 。

7、利用逐点插入建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素30要进行 次元素间的比较。

8、已知一个无向图如下图所示:则从顶点0出发进行深度优先搜索遍历，得到的顶点序列为 。

0 2 1 3

4 6 5

(第二题，第5、6小题图) 第二题，第8小题图

9、拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，下图所示为一有向图，请写出它的一个拓扑序列 。

1 2 3 4 5 6 7 (第二题，第9小题图)

10、设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序

查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为 。

《 数据结构与算法 》试卷 第 3 页 共 8 页

三、算法分析题（每小题15分，共30分）

(阅读以下说明和代码，并将正确的代码填在空格内。)

得分 1、[说明]一般的树结构常采用孩子-兄弟表示法表示，即用二叉链表存储，链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟。函数LevelTraverse()的功能是对树进行层次遍历，对树层次遍历时使用了队列结构，实现队列基本操作的函数原型如下表所示：

函数原型 Void InitQueue(Queue *Q) Bool IsEmpty(Queue Q) Void EnQueue(Queue *Q,TreeNode p) Void Dequeue(Queue *Q,TreeNode *p) 说明 初始化队列 判断队列是否为空，若是返回TRUE，否则返回FALSE 元素入队列 元素出队列 Bool、Status类型定义如下：

typedef enum {FALSE=0，TRUE=1} Bool；

typedef enum {OVERFLOW=-2，UNDERFLOW=-1，ERROR=0，OK=1} Status； 树的二叉链表结点定义如下： typedef struct Node { char data；

struct Node *firstchild，*nextbrother； }Node，*TreeNode； [算法]

Status LevelTraverse(TreeNode root)

{/*层序遍历树，树采用孩子-兄弟表示法，root是树根结点的指针*/ Queue tempQ；

TreeNode ptr,brotherptr； If(!root) return ERROR； InitQueue(&tempQ) ；

； brotherptr=root->nextbrother； while (brotherptr) {

EnQueue(&tempQ,brotherptr) ；

； }/*end while */

while ( ) {

； printf(“%c\”,ptr->data) ；

if ( ) continue； ； brotherptr = ptr->firstchild->nextbrother； while (brotherptr) {

EnQueue(&tempQ,brotherptr) ；

}/*end while */ }/*end while */ return OK;

}/*LevelTraverse */

《 数据结构与算法 》试卷 第 4 页 共 8 页

2、[说明]若一个矩阵中的非零元素数目很少且分布没有规律，则称之为稀疏矩阵。对于m行n列的稀疏矩阵M，进行转置运算后得到n行m列的矩阵MT。为了压缩稀疏矩阵的存储空间，用三元组(即元素所在的行号、列号和元素值)表示稀疏矩阵中的一个非零元素，现用一维数组逐行存储稀疏矩阵中的所有非零元素(也称为三元组顺序表)。

函数TransposeMatrix(Matrix M)的功能是对用三元组表表示的稀疏矩阵M进行转置。

为了将M中的每个非零元素直接存入其转置矩阵MT三元组顺序表的相应位置，需先计算M中每一列非零元素的数目(即MT中每一行非零元素的数目)，并记录在向量num中；然后根据以下关系，计算出矩阵M中每列的第一个非零元素在转置矩阵MT三元组顺序表中的位置：

cpot[0] = 0； cpot[j]=cpot[j-1]+num[j-1] /*j为列号*/ 类型ElemType 、Triple和Matrix定义如下： typedef int ElemType；

typedef struct {/*三元组类型*/

int r,c； /*矩阵中非零元的行下标和列下标*/ ElemType e；/*矩阵元素的值*/ }Triple；

typedef struct {/*矩阵的三元组顺序表存储结构*/

int rows,cols,elements；/*矩阵的行数、列数和非零元素数目*/ Triple data[MAXSISE] ； }Matrix； [算法]

int TransposeMatrix(Matrix M) {

int j,q,t;

int *num,*cpot;

Matrix MT; /*MT是M的转置矩阵*/

num = (int *)malloc(M.cols*sizeof(int)); cpot = (int *)malloc(M.cols*sizeof(int)); if (!num || !cpot) return ERROR;

MT.rows = ；/*设置转置矩阵MT的行数、列数和非零元数目*/ MT.cols = ； MT.elements = M.elements； if (M.elements >0 ){

for(q=0；qfor (t=0;tfor (j=1；jj= ； /*取矩阵M的第一个非零元素的列号存入j*/

q= ；/*q为该非零元在MT三元组顺序表中的位置*/ MT.data[q].r = M.data[t].c； MT.data[q].c = M.data[t].r； MT.data[q].e = M.data[t].e；

；/*计算M中第j列的下一个非零元素的目的位置*/ }/*end for */ }/* end if */

free(num)； free(cpot)；

return OK； }

《 数据结构与算法 》试卷 第 5 页 共 8 页

四、应用题（每小题10分，共30分）

得分

1、设F={T1，T2，T3}是森林（如下图所示），试将它转换为二叉树，并画出所对应的二叉树。

1 2 5 T1

4 6 7 T2

第四题，第1小题图

8 9 11 14 15 T3 10 13 3 12 2、以关键码序列(46,74,53,14,26,38,86,65,27,34)，假设以第一个记录作为枢轴(或支点)，写出快速排序每一趟排序结束时的关键码状态。

《 数据结构与算法 》试卷 第 6 页 共 8 页

3、某赋权有向图如下图所示。用迪杰斯特拉（Dijkstra）算法思想，求源点A到各其余顶点的最短路径及路径长度。

10 E 15 D 4 F 10 30 B 2 4 C 15 A 20 10 第四题，第3小题图

《 数据结构与算法 》试卷 第 7 页 共 8 页

五、算法设计题（每小题10分，共10分）

(阅读说明，请从下列两题算法设计题中，任选做一题)

[说明]二叉树的存储结构采用如下所示的二叉链表。 Typedef char ElemType； typedef struct BTNode { ElemType data；

struct BTNode *lchild，*rchild； } BTNode，*BTree；

1、设计算法计算一棵二叉树中叶子结点和非叶子结点的个数。 2、设计算法计算一棵二叉树的深度。

得分 《 数据结构与算法 》试卷 第 8 页 共 8 页