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

学号               姓名             班级            

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

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

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

（     ）2、计算机算法必须具备输入、输出和       等5个特性。

A、可行性、可移植性和可扩充性               B、可行性、确定性和有穷性

C、确定性、有穷性和稳定性                    D、易读性、稳定性和安全性

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

A、8                    B、63.5               C、63                D、7

（     ）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;            B、q->next=s; s->next=p;

C、p->next=s->next; 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、需经常修改Ｌ中的结点值        B、需不断对Ｌ进行删除插入

C、Ｌ中含有大量的结点            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的值是          。

Ａ、i(i-1)/2+j-1                           

Ｂ、i(i-1)/2+j     

Ｃ、i(i+1)/2+j-1                           

Ｄ、(i+1)/2+j

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

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

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

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

Ｄ、数组可以看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作

（    ）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    s+=B[i][j];

sum=s;

四、综合题（共22分）。

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

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

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

4、已知图的邻接矩阵为：

（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=BiTreeDepth(b->rchild);            /*求右子树的高度为rchilddep*/     return (lchilddep>rchilddep)?                      (lchilddep+1): (rchilddep+1);      }}