数据结构(第1~7章单元测试)

数据结构第1~7章单元测试题

学号 姓名 班级

一、选择题（每小题2分，共38分。每小题只有一个正确答案）

（ ）1、数据结构中，与所使用的计算机无关的是数据的 结构。 A、存储

B、物理 C、逻辑 D、物理和存储

B、可行性、确定性和有穷性 D、易读性、稳定性和安全性

（ ）2、计算机算法必须具备输入、输出和 等5个特性。 A、可行性、可移植性和可扩充性 C、确定性、有穷性和稳定性 个元素 A、8

B、63.5 C、63

D、7

（ ）3、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动

（ ）4、在n个元素的顺序表中，算法的时间复杂度是O（1）的操作是 。 A、在第i个元素后插入一个新元素（1≤i≤n） B、删除第i个元素（1≤i≤n） C、将n个元素从大到小排序

D、访问第i个元素（1≤i≤n）和求第i个元素的直接前驱（2≤i≤n）

（ ）5、在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则须执行 。

A、s->next=p->next; p->next=s; C、p->next=s->next; s->next=p;

B、q->next=s; s->next=p;

D、p->next=s; s->next=q;

（ ）6、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用 存储方式节省时间。 A、单链表

B、双向链表

C、单循环链表

D、顺序表

（ ）7、对于头指针为head的带头结点的单链表，判定该表为空表的条件是 。 A、head==NULL

B、head->next==NULL C、head->next=head D、head!=NULL

（ ）8、将长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度 。A、O(1)

B、O(n)

C、O(m)

D、O(m+n)

（ ）9、 线性表Ｌ在 情况下适用于使用链式结构实现。 A、需经常修改Ｌ中的结点值 C、Ｌ中含有大量的结点

B、需不断对Ｌ进行删除插入 D、Ｌ中结点结构复杂

（ ）10、设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是 。 A、 a，b，c，d

B、c，d，a，b

C、b，c，d，a D、b，c，a，d

（ ）11、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 。

A、1和 5 B、 2和4 C、4和2 D、 5和1 （ ）12、串是一种特殊的线性表，其特殊性体现在 。

A、可以顺序存储 B、数据元素是单个字符 C、可以链式存储 D、数据元素可以是多个字符

（ ）13、设有两个串p和q，求q在p中首次出现的位置的运算称作 。 Ａ、连接 Ｂ、模式匹配

Ｃ、求子串 Ｄ、求串长

（ ）14、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≥j), 在一维数组B中下标k的值是 。

a1,1a2,1Ｂ、i(i-1)/2+j AＣ、i(i+1)/2+j-1 an,1Ａ、i(i-1)/2+j-1 Ｄ、(i+1)/2+j

（ ）15、下列说明正确的是 。

a2,2an,2an,nＡ、若采用三元组存储稀疏矩阵，把每个元素的行下标与列下标互换，就完成了对该矩阵的转置运算

Ｂ、十字链表不是顺序存储结构

Ｃ、稀疏矩阵压缩存储后，必会失去其随机存储功能

Ｄ、数组可以看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作 （ ）16、二叉树是非线性数据结构，所以（ Ａ、它不能用顺序存储结构存储; Ｂ、它不能用链式存储结构存储;

Ｃ、顺序存储结构和链式存储结构都能存储; Ｄ、顺序存储结构和链式存储结构都不能使用

（ ）17、 以二叉链表作为二叉树存储结构，在具有n 个结点的二叉链表中( n>0) ，空链域的个数为（ A、2n-1

）。 B、n-1

C、n+1

D、2n+1

）。

（ ）18、具有65个结点的完全二叉树其深度为（ A、8

B、7

C、6

）。

D、5

（ ）19、 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历序列是（ ）。

A、acbed B、decab C、deabc D、cedba

二、判断题（每小题2分，共20分。正确的在题前括号内打“√”，错误的打“×”）

（ ）1、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

（ ）2、递归过程或函数调用时，处理参数及返回地址，要用一种称为栈的数据结构。 （ ）3、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

（ ）4、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（ ）5、设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有front=11，rear=19，循环队列中有元素8个。

（ ）6、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ ）7、二叉树中每个结点的两棵子树是有序的。

（ ）8、具有700个结点的完全二叉树有350个叶子结点。

（ ）9、树的路径长度最短的树是完全二叉树，哈夫曼树又称最优二叉树，也就是所有路径长度最短的树，所以完全二叉树就是哈夫曼树。

（ ）10、将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。

三、分析下面各程序段的时间复杂度（每小题4分，共8分）

1、s=0; 2、i=1; for (i=0; ifor(j=0; j四、综合题（共22分）。

1、假设用于通信的电文由８个字母A，B，C，D，E，F，G，H组成，各字母在电文中出现的频率分别为：７，１９，２，６，３２，３，２１，１０。试为这８个字母设计哈夫曼编码。

2、把如图所示的树转化成二叉树。

3、下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。

4、已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 53318121191141466631625V10 0 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）以顶点V1为出发点的唯一的广度优先遍历； （2）该图唯一的拓扑有序序列。

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

1、已知有一个单链表(带头结点),其头指针为head,请编写一个函数计算单链表中结点的个数,并分析你的算法的时间复杂度。

2、请编写一个算法，对单链表(带头结点)实现就地逆置（设头指针为head）。 void convert(linklist head){ //带头结点的单链表head就地逆置 LNode *p, *q;

p=head->next; //指向开始结点 head->next=NULL; //逆置后初表为空

while(p) //p为NULL，表示已经全部逆置 {q=p->next; //p指向下一个需要逆置的结点 p->next=head->next; //将需要逆置结点插入头结点后面 head->next=p; p=q; } return OK; }//convert

3、二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树的深度。

int BiTreeDepth(BiTree b) { int lchilddep,rchilddep;

if (b==NULL) return(0); /*空树的高度为0*/ else {

lchilddep=BiTreeDepth(b->lchild);

/*求左子树的高度为lchilddep*/

/*求右子树的高度为rchilddep*/

rchilddep=BiTreeDepth(b->rchild);

return (lchilddep>rchilddep)?

(lchilddep+1): (rchilddep+1); } }