数据结构期末试卷

《数据结构（乙）》课程期末考试试卷（B）答案

开课分院： 信息分院 ，考试形式：闭卷

考试日期：__ 2008 ___年__12__月__28__日，考试所需时间： 120 分钟

考生姓名 学号 考生所在分院： 专业班级： . 题序 题型 得分 评卷人 一 单项选择题 二 填空题 三 问答题 四 程序阅读题 五 程序编写题 总 分 一、单项选择题（本大题共10小题，每小题2分，共20分）

( B )（1）下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？

A．直接插入排序 B．直接选择排序 C. 快速排序 D.起泡排序

( A )（2）已知循环队列的存储空间为数组data[18]，且当前队列的头指针和尾指针的值分别为7和2，则该队列的当前长度为？ A．13 B．5 C．9

D．18

( C )（3）在单链表中，已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？

A．s-> next = p； p-> next = s； B．s-> next = p-> next；p = s； C．s-> next = p-> next；p-> next = s； D．p-> next = s； s-> next = p； ( D )（4）一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为？

A. 38，40，46，56，79，84 B. 40，38，46，79，56，84 C. 40，38，46，84，56，79 D. 40，38，46，56，79，84

( B )（5） 任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序？

A.发生改变 B.不发生改变 C.不能确定 D.以上都不对 命题（组）老师签名：____________________ 年 月 日

分院主管教学院长或首席主讲教授签名：_______________ 年 月 日

第1页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

( C )（6）一棵含18个结点的二叉树的高度至少为

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

( B )（7）在用于表示无权有向图的相邻矩阵中，对第j列的非0元素个数进行累加，可得到第j个顶点的？

A．出度 B．入度 C．权值 D．连接边个数 ( C )（8）若进栈序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？

A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1 ( A )（9）按照二叉树的定义，具有3个结点的不同形状的二叉树有几种？

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

( D )（10）对一个满二叉树，m个树叶，n个结点，深度为h，则?

A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1

二、填空题（本大题共10小空，每小空2分，共20分）

1. 在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。 2. 队列是线性结构，只能在队尾插入元素和队首删除元素。

3. 某二叉树的前序遍历为abdgcefh，中序遍历为dgbaechf，则后序遍历的为gdbehfca。 4. 一棵二叉树的第i（i≥1）层最多有2i-1个结点。

5. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是p->next=p->next->next。

6. 一棵二叉树中双分支结点数为15，单分支结点数为30个，则叶子结点数为16个。 7. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要n-1条边。

三、问答题（本大题共4小题，每小题6分，共24分）

1. 设字符a,b,c,d,e,f的使用权值分别是7, 9, 12, 22, 23, 27，画出Huffman树，并写出a,b,c,d,e,f的Huffman编码。 Huffman编码为

a: 1110 b: 1111 c: 110 d: 00 e: 01 f: 10

第2页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

2. 已知有向图的邻接矩阵如图所示，要求完成如下任务： （1）请画出此有向图；（2）给出该有向图的邻接表。

0000A0000010001000110010010000 00000000000100000001000010001000000有向图为： 邻接表为：

3．二叉树如图所示，要求完成如下任务：

（1）画出该二叉树的中序线索二叉树；（2）画出该二叉树对应的森林。。

第3页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

中序线索二叉树为： 该二叉树对应的森林为：

4．已知带权有向图如下所示，用Dijkstra算法求从顶点V1到其他各顶点的全部最短路径，请给出算法的处理过程。

第4页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

四、程序阅读题（本大题共2小题，每小题6分，共12分） 1. 完成顺序表的删除。

#include struct sqlist { int list[50]; int size; };

void remove(struct sqlist *p,int i) { int j; if (i<0 || i>=p->size) printf(\"错误\"); else { for (j=i; jsize-1 ; j++) p->list[j]=p->list[j+1] ; p->size--;

第5页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

} printf(\"此线性表为：\"); for (i=0;isize;i++) printf(\"%d->\}

void main() { int i,x; struct sqlist l; l.size=0; printf(\"请输入4个数据：\\n\"); for (i=0;i<4; i++) { scanf(\"%d\ l.size++; } printf(\"输入位置:\"); scanf(\"%d\ remove(&l,i) ; }

2. 完成对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。 void SelectSort(LinkedList L) {

LinkedList p, q, min; int rcd;

p= L->next ; while(p!=NULL) {

min=p; q=p->next;

while(q!=NULL)

{

if( q->data< min->data ) min=q; q=q->next; }

if( min!=p )

{

rcd=p->data;

p->data=min->data; min->data=rcd; }

p=p->next ; } }

五、程序编写题（本大题共2小题，每小题12分，共24分） 1.优化的冒泡排序的子函数实现。 void bubblesort(int a[20], int n)

第6页（共7页）

考生姓名 学号 考生所在分院： 专业班级： .

{

int i,j,x;

bool NoSwap; for(i=1;iNoSwap=true; for(j=n-1;j>=i;j--) if(a[j]if(NoSwap) return; } }

2.线性单链表的生成实现，在已给的程序基础上编写生成子函数，结点数据从键盘输入。 #include typedef struct LNode{ char data; struct LNode *next; }* LinkList;

LinkList creatlist() {

LinkList Head,P,Q; P=new(struct LNode); Head=P;

P->next=NULL;

cout<<\"输入整个链表的结点信息（!作为结束）:\\n\";

do{ Q=new(struct LNode); cin>>Q->data; Q->next=NULL; P->next=Q; P=Q; }while(Q->data!='!'); return (Head); }

void main(void) { LinkList List; List=creatlist( ); }

第7页（共7页）