2007-2008第1学期数据结构基础期末考卷 - 06级 2

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

浙江大学城市学院

2007 — 2008 学年第 一 学期期末考试试卷

《 数据结构基础 》

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

1．对于给定的n个元素，可以构造出的逻辑结构由 这几种结构。

A．动态结构和静态结构 B．线性表、栈、队列、字符串

C．顺序结构、链表结构、线性结构、非线性结构 D．集合、线性结构、树形结构、图形结构

2．算法效率的度量的一种是时间复杂度，它与 直接相关。 A．数据类型 B．数据结构 C．算法 D．空间复杂度 3．一个顺序表所占存储空间的大小与 无关。

A．顺序表长度 B．结点类型 C．结点中各数据域的类型 D．结点的存放次序 4．线性表是具有n个 的有限序列。

A．表元素 B．字符 C．数据项 D．数据元素 5．线性表在 时，宜采用链式存储方式。

A．需不断对其进行插入删除 B．需经常对其进行查找 C．无足够连续存储空间 D．其结点含大量信息

6．设输入元素为1、2、3、P和A，输入次序为123PA，元素经过栈后得到各种输出序列，则可以作为高级语言变量名的序列有 种。

A．4 B．5 C．6 D．7

第 1 页 共 6 页

7．一个队列的入队序列为a，b，c，d，则该队列的输出序列是 。

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

8. 按照二叉树定义，具有3个结点的二叉树共有 种形态。

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

9．如果用二叉链表来表示一棵具有n（n>1）个结点的二叉树，则在二叉链表中 。 A．至多有n-1个非空的右指针域 B．至少有2个空的右指针域 C．至少有2个非空的左指针域 D．至多有n-1个空的右指针域 10．在高度为h的完全二叉树中， 。 A．第i(1≤i＜h)层上结点的度都为2 B． 第i(1≤i＜h)层上有2i-1个结点 C．度为0的结点都在第h层上 D．不存在度为1 的结点

11．二叉树若用顺序存储结构（数组）存放，则下列四种运算中的 最容易实现。 A．先序遍历二叉树 B．判断两个结点是不是在同一层上 C．层次遍历二叉树 D．根据结点的值查找其存储位置 12. 对某个无向图的邻接矩阵来说，下列叙述正确的是 。 A．第i行上的非零元素个数和第i列上的非零元素个数一定相等 B．矩阵中的非零元素个数等于图中的边数 C．第i行与第i列上的非零元素的总数等于顶点vi的度数 D．矩阵中非全零行的行数等于图中的顶点数

13. G是一个非连通无向图，共有15条边，则该图至少有 个顶点。

A．16 B．9 C．8 D．7 14. 在一个图中，所有顶点的度数之和等于所有边数的_____倍。

A．1/2 B．1 C．2 D．4 15．图的广度优先搜索算法的实现中需要使用 作为辅助工具。 A．栈 B．队列 C．线性表 D．链表

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

1．线性结构中元素之间存在 ⑴ 关系，树形结构中元素之间存在 ⑵ 关系，图形结构中元素之间存在 ⑶ 关系。

2．若顺序表中第一个元素的存储地址是100，表中每个元素的存储长度为4，则第5个元素的存储地址是 ⑷ 。

3．单链表中，q在前p在后的指向相邻的两个结点，要在q，p之间插入s所指的结点，其实现的语句应是 ⑸ q->next=s,s->next=p 。

4．将f(n)=1+1/2+1/3+ … +1/n用递归实现，其递归体（递归函数）是f(n)= ⑹ ，递归出口是f(1)= ⑺ 。

5．循环队列A[0..m-1]存放其元素，用front和rear分别表示队头和队尾，则循环队列满的条件是 ⑻ ，循环队列空的条件是 ⑼ 。

6．在二叉树的第i（i≥1）层上至多有 ⑽ 个结点，深度为k（k≥1）的完全二叉树至多 ⑾ 个结点，最少 ⑿ 个结点；如果二叉树的终端结点数为n0，度为2的结点数为n2，则n0 =___⒀___。 得分 7．已知一棵二叉树的先序序列和中序序列分别为GFDBHCEA和DFHBGCAE，则该二叉树的后序序列为 ⒁ ，层序序列为 ⒂ ，该二叉树的深度为 ⒃ 。

第 2 页 共 6 页

8．一个n个顶点的有向强连通图最多有 ⒄ 条边，最少有 ⒅ 条边。 一个n个顶点的无向连通图最多有 ⒆ 条边，最少有 ⒇ 条边。

三．解答题 ( 本大题共 3 题，每题 5 分，共 15 分) 得分

1．用一维数组a[7] 顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：22，30，16，36，58，其中22是队首， front值为5，请画出对应的存储状态图，当连续做两次出队运算后，再做两次入队运算，让元素80，55依次进队，请再画出对应的存储状态图。

2．一棵二叉树的结点数据采用顺序存储结构存储在如下的数组中。

0

(1) 画出该二叉树的二叉链表图示

(2) 写出该二叉树的先序、中序和后序序列 (3) 把改二叉树转换为森林

3．已知一个有向图的邻接链表存储结构如下：

1 V1 2 V2 3 V3 4 V4 5 V5 6 V6 4 6 3 ∧ 1 a 2 b 3 c 4 5 d 6 e 7 8 9 10 11 12 13 14 f g h 2 3 6 ∧ 5 5 ∧ 4 ∧

(1) 根据有向图的深度优先遍历算法，写出从顶点v1出发所得到的顶点序列。 (2) 根据有向图的广度优先遍历算法，写出从顶点v1出发所得到的顶点序列。

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

1．设h为不带头结点的单链表，说明下列算法的功能：

void func(LNode *h) {

if(h!=NULL) { func(h->next); cout<data; }

}

第 3 页 共 6 页

2．说明下列算法的功能：

int func() {

InitStack(S); //初始化栈 InitQueue(Q); //初始化队列

while((c=getchar())!=’\\n’) { Push(S,c);

EnQueue(Q,c); }

while(!StackEmpty(S)) { Pop(S,a); DeQueue(Q,b);

if(a!=b) return 0; }

return 1; }

3．设A,B为两个元素依次递增有序的顺序表，下列算法用于构造一个新的顺序表C，阅读算法func，请写出顺序表C的各个元素值。

设顺序表A,B的元素值为如下： A.list[]={9,12,15,18,21,24,27,30,33,36,46} B.list[]={8,12,16,18,23,24,27,39} List类型结构为：

struct List{

ElemType *list; //动态存储空间的基地址，指针 int size; //线性表当前实际长度 int MaxSize; //当前线性表分配的长度 };

void func(List A,List B,List &C) { int i=0,j=0,k=0; while(iB.list[j]) j++; if(A.list[i]==B.list[j]) { C.list[k++]=A.list[i]; C.size++; i++; j++; } } }

第 4 页 共 6 页

得分 五．程序填空题 (本大题共 2 题7空，每空 2 分，共 14 分)

1．有一个带头结点单链表L，其函数值非递减排列，下列函数实现删除该单链表L 中多余的元素值相同的结点。

int DeleteList_L(LNode *&L){

LNode *p,*q;

if ( ① ) return 0; //L为空链表 p=L->next; //p指向第一个结点

q=L;

while( ② ) {

if (p->data!=p->next->data) p=p->next; else { ③ ; ④ ; free(q); } }

return 1; }

2. 下面函数计算链表结构的二叉树中有双孩子的结点数。 struct BTreeNode {

ElemType data; BTreeNode *left; BTreeNode *right; }; int twochild(BTreeNode *BT) { int num1, num2; if (BT==NULL) ⑤ ; else if ( ⑥ ) return twochild(BT->right);

else if (BT->left != NULL && BT->right == NULL)

return twochild(BT->left); else { num1=twochild (BT->left); num2=twochild (BT->right); return ⑦ ; }

}

第 5 页 共 6 页

得分 六．程序设计题 (本大题共 2 题，第一题 7 分，第二题 14 分，共 21 分)

1． 在一个不带头结点的链式队列中只设置队尾指针，不设置队首指针，并且让队尾结点的指针

域指向队首结点（称此为循环队列），试写出在循环链队上的入队操作的算法。 函数原形为： int LEnQueue(LNode *h,ELemType x) 结点类型如下：

struct LNode { ElemType data; LNode *next; } ;

2． 编写算法求二叉树中以元素值为x的结点为根的子树的深度。

设函数原形为：int Get_Sub_Depth(BTreeNode *T , ElemType x)

BTreeNode结构如下：

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

提示：可再写一函数实现求二叉树的深度。

第 6 页 共 6 页

得分 六．程序设计题 (本大题共 2 题，第一题 7 分，第二题 14 分，共 21 分)

1． 在一个不带头结点的链式队列中只设置队尾指针，不设置队首指针，并且让队尾结点的指针

域指向队首结点（称此为循环队列），试写出在循环链队上的入队操作的算法。 函数原形为： int LEnQueue(LNode *h,ELemType x) 结点类型如下：

struct LNode { ElemType data; LNode *next; } ;

2． 编写算法求二叉树中以元素值为x的结点为根的子树的深度。

设函数原形为：int Get_Sub_Depth(BTreeNode *T , ElemType x)

BTreeNode结构如下：

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

提示：可再写一函数实现求二叉树的深度。

第 6 页 共 6 页

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