数据结构期末考卷13-14

_…__…__…__…__…__…__…__…__…_：…名…姓…… __…__…__…__…__…__…__…_：…号线..学… _…__…__…__…__…__…__ 订.__…__…：…级…班… …__…__装_..__…__…__…__…__…__…__…__…：…业…专… _…__…__…__…__…__…__…：…级…年……诚信应考 考出水平 考出风格

浙江大学城市学院

2013 — 2014 学年第 一 学期期末考试试卷

《 数据结构基础 》

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

1. 数据的 包括集合、线性结构、树形结构和图形结构四种基本类型。 A. 存储结构 B. 逻辑结构 C. 基本运算 D. 算法描述 2. 中任何两个结点之间都没有逻辑关系。 A. 树形结构 B. 集合

C. 图形结构 D. 线性结构 3. 下面的程序段违反了算法的 原则。 void fun() { int x=2;

while (!(x%2)) x=x*2; printf(“%d”,x);

}

A. 健壮性 B. 确定性 C. 可行性 D. 有穷性 4. 算法分析的两个主要方面是 。 A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性

D. 数据复杂性和程序复杂性

第 1 页 共 6 页

5. 用数组表示线性表的优点是 。 A. 便于插入和删除操作 B. 便于随机存取

C. 可以动态地分配存储空间

D. 不需要占用一片相邻的存储空间

6. 循环链表的主要优点是 。 A. 节约存储空间

B. 已知某个结点的位置后，能够很容易找到它的直接前驱 C. 在进行插入、删除运算时，能更好的保证链表不断开 D. 从表中的任意结点出发都能访问到任何一个结点

7. 可以用带表头附加结点的链表表示线性表，也可以用不带头结点的链表表示线性表，前者最主要的好处是 。 A. 可以加快对表的遍历 B. 节省存储空间

C. 使空表和非空表的处理统一 D. 可以提高存取表元素的速度

8. 在头指针为h且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p->next->next==h，则 。

A. p指向头结点 B. p指向尾结点

C. *p的直接后继是头结点 D. *p的直接后继是尾结点 9. 线性表中，只有直接前驱而无后继的元素是 。 A. 首元素 B. 尾元素 C. 中间元素 D. 全部元素 10. 以下不是栈的基本运算的是 。

A. 删除栈顶元素 B. 删除栈底元素 C. 判断栈是否为空 D. 将栈置为空栈

11. 若用一个大小为6的数组来实现循环队列，且当前rear和fornt的值分别为1和4。从当前队列中删除一个元素，再加入两个元素后，rear和front的值分别为 。 A. 3和5 B. 2和0 C. 0和2 D. 5和3 12. 最不适合用作链队的链表是_____。 A. 只带队头指针的非循环双链表 B. 只带队头指针的循环双链表 C. 只带队尾指针的循环双链表 D. 只带队尾指针的循环单链表

13. 最不适合用作栈的链表是 。 A. 只有表头指针没有表尾指针的循环双链表 B. 只有表尾指针没有表头指针的循环双链表 C. 只有表尾指针没有表头指针的循环单链表 D. 只有表头指针没有表尾指针的循环单链表

14. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程效率 。

A. 高 B. 低 C. 相同 D. 无法确定

第 2 页 共 6 页

15. 设n和m为一棵二叉树上的两个结点，中序遍历时，n在m后的条件是 。 A. n在m的右子树上 B. n是m祖先 C. n在m的左子树上 D. n是m子孙

16. 已知一棵普通树的广义表表示为a(b, c(e(h, i, j), f), d(g))，则此树的深度为 。 A. 2 B. 3 C. 4 D. 5

17. G是一个非连通无向图，共有21条边，则该图至少有___________个顶点。 A. 7 B. 8 C. 9 D. 23 18. 用邻接表存储图，所用的空间大小___________。

A. 与图的顶点数和边数都有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关

二．填空题 (本大题共 10 题，每题 2 分，共 20 分)

1. 数据结构主要研究三方面的内容：数据的逻辑结构、 。 2. 计算机算法指的是解决问题的有限运算序列，它必具备输入、输出、有穷性和 这五个特性。

3. 下列算法的时间复杂度为 。 得分 int test(int n) { int s=1;

while(s<=n) s=s*2; return s; }

4. 在单链表中，指针p指向某中间结点，实现“删除p结点的后继结点”的语句是 。 5. 向一个栈顶指针为top的链式栈中插入一个s所指的结点时，则执行 。 6. 在一个非空的链式队列中，假设f 和r 分别为队头和队尾指针，则实现出队列运算并将删除结点元素值赋给x 的语句是 。

7. 栈s的初始状态为空，6个元素a, b, c, d, e, f 依次入栈，若出栈的顺序是b, d, c, f, e, a，则栈s的容量至少应该是 。 8. 已知二叉树的后序遍历是 d a b e c，中序遍历是 d e b a c，则其前序遍历是 。 9. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m、n和p，则与森林F对应的二叉树根结点的右子树上的结点个数是 。 10. 对于稠密图，适合使用 存储结构。 得分 三．解答题 ( 本大题共 3 题，每题 6 分，共 18 分)

1. 设栈S的初始状态为空，队列Q的初始状态如下图所示：

a1 a2 a3 a4 ↑ ↑ 队头 队尾

第 3 页 共 6 页

若对栈S和队列Q进行以下两步操作：

① 对队列Q依次执行出队列操作，并将出队列的元素依次入栈S，直到Q为空； ② 依次将栈S中的元素入队列Q，直到S为空； 请画出在执行上述两步操作后，队列Q的状态图。

2．设某二叉树用顺序存储结构（即一维数组）存储的示意图如下： 0 1 2 3 4 5 6 7 8 9 A B C D E F G

① 请画出该二叉树的二叉链表存储结构示意图； ② 写出该二叉树的中序遍历序列。

3．已知图G的邻接表如下图所示：

① 写出从顶点v1出发的深度优先搜索序列； ② 画出该图的邻接矩阵存储结构示意图。

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

1．阅读下列程序，说明算法的功能： typedef struct node{ ElemType data; struct node *next; }LNode;

void f1(LNode *&h) {

LNode *p=NULL, *q=h, *r; while (q!=NULL ) { r=q->next; q->next=p; p=q; q=r; } h=p; }

第 4 页 共 6 页

2．已知线性表中的元素按值递增有序排列，阅读下列程序，说明算法的功能： typedef struct { ElemType *list; int size;

int MaxSize; }SeqList;

void f2(SeqList &L, ElemType m, ElemType n) { int i=0, j;

while(i

while (j

while (j

3．阅读下列程序，说明算法的功能：

int f3(int x[], int m) {

if (m==1) return x[0];

else return f3(x, m-1)+ x[m-1]; }

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

1. 设二叉树用三叉链表存储结构存储，下列算法是在二叉树BT中查找元素x，若找到，则返回x的双亲结点的地址，否则返回NULL。请在空白处填入适当的语句，使该算法完整。 typedef struct node{ ElemType data;

struct node *left, *right, *parent; } BTreeNode;

BTreeNode *t1(BTreeNode *BT, ElemType x) { if (BT==NULL) return ① ; if (BT->data==x )

return BT->parent; p=t1(BT->left, x); if (p!=NULL) return p;

p=t1( ② ); if (p!=NULL)

return ③ ; return NULL; }

第 5 页 共 6 页

2. 下列算法是由无向图的邻接表生成邻接矩阵，请在空白处填入适当的语句，使该算法完整。 typedef struct Node { int adjvex; struct Node *next; } edgenode; //边结点

typedef edgenode *adjlist[ MaxVertexNum ]; //邻接表存储结构

typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵存储结构 void t2(adjlist GL, adjmatrix GA, int n) { //由GL建立GA，n是图的顶点数

int i, j; edgenode *p; for ( i = 0 ; i < MaxVertexNum; i++ ) //初始化邻接矩阵 for ( j = 0 ; j < ④ ; j++ )

GA[i][j] =0;

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

if (GL[i] != NULL) { p = GL[i]; while ( ⑤ ){

//访问邻接表

j= p->adjvex ; ⑥ ; p = p->next; } } }

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

1. 设链式队列用只带队头指针的循环双向链表表示，如下图所示:

front

要求：

① 写出该链式队列的结点结构定义（即循环双向链表的结点结构定义）； ② 写出在该循环双链链式队列上进行入队列操作的算法（函数）。

2. 设以二叉链表方式存储二叉树BT，要求： ① 写出二叉链表的结点结构定义； ② 写一算法（函数），由二叉树BT生成一棵新的二叉树，该新二叉树是将BT各结点的左右孩子交换后生成的（即BT任一结点的左孩子在新二叉树中是右孩子，右孩子是新二叉树的左孩子），要求返回新生成的二叉树根结点的地址（注意：原二叉树BT需保持不变）。

第 6 页 共 6 页

本文来源：https://www.bwwdw.com/article/hm2h.html