数据结构期末考卷09级

浙江大学城市学院

2009 — 2010 学年第 二 学期期末考试试卷

《 数据结构基础 》

开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2010 年 7 月 5 日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 总 分 得分 评卷人 得分 一．选择题 (本大题共 20 题，每题 1 分，共 20 分)

1. 评价一个算法有五个方面，其中对非法数据的输入的处理能力是指算法的 。 A．可读性 B．正确性 C．可行性 D．健壮性

2. 设求解同一问题有四种算法，这四种算法各自的时间复杂度分别为O(n2), O(nlogn), O(2n)，O(n)，则这四种算法按时间效率由高到低的排列次序为 。 A. O(n2), O(nlogn), O(2n), O(n) B. O(n), O(n2), O(nlogn), O(2n), C. O(n), O(nlogn), O(n2), O(2n) D. O(2n), O(n2), O(nlogn), O(n)

3. 在数据结构实验用到的C++语言中，若需在程序中使用输入输出流对象，则程序的头部应加上 命令。

A. #include < math.h > B．#include < fstream.h > C. #include < stdio.h > D．#include < iostream.h >

4. 在C++语言中，有一对运算符（非函数）可进行动态存储空间的分配和删除，他们是是 。

A. cin 和 cout B．malloc 和 free C. calloc 和 free D．new 和 delete 5. 数据结构主要研究三个方面的内容： 。 A．数据的逻辑结构、物理结构、运算 B．线性结构、图结构、树结构 C．正确性、可行性、有穷性 D．线性表、栈、队列

第 1 页 共 6 页

6. .以下数据结构中， 是线性结构。

A. 有向图 B. 栈 C. 二叉树 D. 树 7. 若要经常对线性表进行插入、删除操作，则最适合的存储结构是 。 A. 静态数组 B. 动态数组 C. 链表 D. 都一样 8. 双链表与单链表相比，主要的优势是 。 A．插入、删除操作更加简单 B．可随机访问

C．访问前驱结点更加方便

D．可以由最后一个结点找到头结点

9．线性表若采用顺序存储结构时，要求内存中存储单元的地址 。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续不连续都可以

10．若对线性表只能进行2种运算：删除最后一个元素、在第一个元素的前面插入新元素，则最适合的存储结构是 。

A．顺序表 B．单链表

C．循环单链表 D．双向循环链表

11．判断一个顺序栈ST(最多元素为MaxSize)为空的条件是 。 A．ST.top==1 B. ST.top==-1

C．ST.top==0 D. ST.top==MaxSize-1

12．设栈s的初始状态为空，6个元素的入栈顺序为e1,e2,e3,e4,e5,e6。若出栈的顺序是e2,e4, e3,e6,e5,e1，则栈s的容量至少应该是 。

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

13．在一个链式队列中，假设f和r分别为队头和队尾指针，则删除结点时执行 。 A. r=f->next; B. r=r->next; C. f=f->next; D. f=r->next;

14. 若同一个问题用递归函数与非递归函数分别实现，通常 。 A．递归函数比非递归函数时间与空间效率要高 B．递归函数比非递归函数时间与空间效率要低

C．递归函数与非递归函数时间与空间效率相同 D．递归函数时间效率低，非递归函数空间效率低 15．树最适合用来表示 。 A．有序数据元素 B．无序数据元素

C．元素之间具有一对多关系的数据元素 D．元素之间无联系的数据元素

16．设n、m为一棵二叉树上的两个结点，进行中序遍历时，若满足条件 ，n必定在m 前遍历。

A. n在m的右子树上 B. n是m 的祖先 C. n在m的左子树上 D. n是m 的子孙

17．已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是 。

A. ACBED B. DEABC C. DECAB D. EDBAC

第 2 页 共 6 页

18. 4个顶点的强连通图，至少有 条边。 A. 3 B. 4 C. 5 D. 6 19．n个顶点的无向完全图，有 条边。

A. n(n-1)/2 B. n(n-1) C. n2 D. n-1 20．在一个图中，所有顶点的度数之和等于所有边数的 倍。 A. 4 B. 2 C. 1 D. 1/2

二．填空题 (本大题共 18 个空，每个空 1 分，共 18 分)

1. 数据的逻辑结构主要包含集合、 ① 、 ② 、 ③ 四种结构。 2. 数据的存储结构主要分为 ④ 和 ⑤ 两种。 3. 数据结构通常可以用一个二元组B=（K，R）来表示，其中K表示 ⑥ ，R表示 ⑦ 。 4. 栈和队列是一种特殊的线性表，根据栈和队列的特征，栈是一种 ⑧ 的线性表，队列是一种 ⑨ 的线性表。

5. 在双向链表中，指针p指向某中间结点，若要在p结点后插入s结点，应执行操作

s->right= ⑩ 、s->left= ⑾ 、p->right->left=s、p->right= ⑿ 。 6. 在单向链表中，指针p指向某中间结点，若要删除p结点的后继，应执行操 ⒀ 。 7. 将有序树T转换成二叉树B后，T中结点的后序遍历次序就是B中结点的 ⒁ 遍历次序。

8. 一棵n个结点的完全二叉树从根结点这一层开始按从上往下，从左到右的顺序把结点依次

存储在数组A[1..n]中。设某个结点在数组中的位置为i，则它的双亲结点的位置是 ⒂ ，若它有左孩子，则左孩子结点的位置是 ⒃ 。 9. 图结构的数据元素之间存在 ⒄ 的关系。

10. 对稠密图来说，应选用 ⒅ 存储结构较合适。

三．解答题 ( 本大题共 3 题，每题 6 分，共 18 分) 得分 得分

1. 用一维数q[10] 顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前

队列中已有8个元素，依次为：a，b，c，d，e，f，g，h，其中a是队首，h是队尾，front的值为7，请画出对应的存储状态图，当连续做四次出队运算后，再让元素x，y，z依次进队，请再画出对应的存储状态图。（说明：需标出front和rear的位置。）

2．有一森林如下，要求：

① 将森林转换为相应的二叉树，画出其示意图。 ② 写出层序遍历该二叉树的结果。

1 2 3 2 4 3 6 5 8 7 5 4 7 6 8 9 11 13 10 12 第 3 页 共 6 页

3. 已知一个无向图的顶点为V0、V1、V2、V3、V4，其邻接矩阵存储结构如下图所示：

0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 0

要求

① 画出该图形。

② 按该邻接矩阵存储结构，分别写出从顶点V0出发的深度优先和广度优先遍历的顶点序列。

四．程序阅读题 (本大题共 3 题，每题 4 分，共 12 分) 得分

1. 阅读下列程序，写出算法的功能： void f1(Queue q, Stack s, int a[], int n) {

int i;

for (i=0; iif (a[i] % 2 ==0 ) EnQueue(q, a[i]); else push(s, a[i]); } }

2. 阅读下列有关线性表操作的程序段，写出程序执行后的输出结果。

List L;

int a[6]={1, 2, 3, 6, 5, 4}; int i, x; InitList(L);

for (i=0; i<6; i++)

InsertList(L, a[i], -1); SortList(L);

x=GetList(L, 6); DeleteList(L, x, 0); InsertList(L, x, 1); TraverseList(L);

3. 阅读下列程序，说明算法的功能： BTreeNode* f3(BTreeNode *BT ) {

if (BT==NULL) return NULL;

第 4 页 共 6 页

else {

BTreeNode* p=new BTreeNode; p->data=BT->data;

p->right= f3(BT->left );

p->left= f3(BT->right ); return p; } }

五．程序填空题 (本大题共 6 个空，每空 2 分，共 12 分) 得分

阅读下列程序，在空白处填入适当的语句，使算法完整。

1. 有一个单链表，其结点的元素值以非递减有序排列，下列函数删除该链表中多余的元素值相同的结点。

设结点结构定义如下： typedef struct Node { ElemType data; struct Node *next; } LNode;

算法为： void delnode( LNode *&head) {

LNode *p=head, *q;

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

if ( p->data != ② ) p=p->next; else {

q=p->next;

③ ; free(q); } } }

2. 下列算法将一个无向图的邻接矩阵转换成邻接表，即由邻接矩阵建立邻接表。 设邻接矩阵结构定义如下：

typedef int adjmatrix[MaxVertexNum] [MaxVertexNum];

设邻接表结构定义如下：

typedef struct node{

int adjvex;

struct node *next;

} edgenode;

typedef edgenode *adjlist[MaxVertexNum];

第 5 页 共 6 页

算法为：void mattolist(adjmatrix a, adjlist &g, int n) { //将n个顶点的无向图由邻接矩阵a建立邻接表g int i, j;

edgenode *p;

for (i=0; ifor (i=0; ifor (j=0; jp->adjvex= ④ ; p->next= ⑤ ; g[i]= ⑥ ;

}

}

得分 六．程序设计题 (本大题共 2 题，每题 10 分，共 20 分)

1. 设二叉树采用链式存储结构，编写一个递归算法释放该二叉树所占用的全部存储空间。 函数原型为：void release（BTreeNode *b） 结点结构定义如下：

struct BTreeNode { ElemType data; BTreeNode *left; BTreeNode *right; };

2. 编写一个算法，利用栈的基本操作返回指定栈中栈底元素。 函数原型为：ElemType bottom( Stack s)

（提示：栈的基本操作包括 InitStack, EmptyStack, Push, Pop, Peek, ClearStack）

第 6 页 共 6 页