数据结构复习题2011

A. 8      B. 127.5    C. 127      D.7

2、带头结点的单链表first为空的判定条件是：( )

A. first==NULL             B. first->link==NULL

C. first->link==first      D. first!=NULL

3、 设某线性链表的头结点指针为L, L->data表示该链表的结点个数，L->next指向该链表的第一个结点，p指向新建立的结点，其类型与L相同。在建立该链表的过程中，若希望L->next始终指向新输入的结点，可采用如下的C语言语句实现：

A. p->next=L->next, L->next=p，L->data++; 

B. p->next=NULL, L->next=p, L->data++;

C. L->data++, L->next=p->next, p->next=L;  

D. 以上都不是。

4、设A、B、C三个字符按先后顺序依次进栈，下面哪个序列为不合法的出栈序列： 

A. A B C          B. A C B       C. B A C       D. C A B 

5、如下陈述中正确的是（    ）

A．串是一种特殊的线性表        B．串的长度必须大于零

C．串中元素只能是字母          D．空串就是空白串

6、在二叉树的第4层上至多有多少个结点： 

    A. 10个       B.  8个        C. 16个   D. 以上都不是。

7、若一棵二叉树具有8个度为2的结点，则该二叉树的叶子个数是（  ）

A.  9        B. 11         C. 7          D. 不确定

8、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(    )

    A. e               B. 2e              C. n2－e         D. n2－2e

9、5个不同的数据元素进行直接插入排序，最多需要进行（　　）次比较。

A.8　 　        B.10　         C.14　  　     D.25

10、设有关键码初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用下列哪种排序方法对初始序列进行第一趟扫描的结果？

   A. 直接插入排序                      B. 二路归并排序

C. 以第一元素为分界元素的快速排序     D. 基数排序

1、数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D，S)，其中D是_________________、S是_________________.

2、在一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动__________个元素。

3、________是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4、 设S=”A;/document/Mary.doc”，则strlen(s)=____________, “/”的字符定位的位置为_______。

5、在哈希造表过程中，处理冲突的方法主要有：________________，________________，________________，________________。

6、所谓稀疏矩阵指的是_______。

7、在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，则称此路径为________________。

8、一棵深度为6的满二叉树有__________个分支结点和___________个叶子。

9、对于n个记录的表进行2路归并排序，整个归并排序需进行_______趟（遍）。

10、数据结构有如下四类基本结构：集合、_________________、_________________、_________________。 

11、在顺序表中插入或删除一个元素，需要平均移动__________元素，具体移动的元素个数与________________有关。

12、栈是一种特殊的线性表，允许插入和删除运算的一端称为 ________。不允许插入和删除运算的一端称为________。

13、____________________________________称为空串；

14、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址，则数组A的体积（存储量）为_______________。

15、一棵具有257个结点的完全二叉树，它的深度为________。

(   )1、数据结构一般包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

(   )2、单链表从任何一个结点出发，都能访问到所有结点

(　 )3、线性表中的每个结点最多只有一个前驱和一个后继。

(   )4、一个n X n的对称矩阵，如果采用压缩存储，其容量为n(n+1)/2。

(   )5、 n个结点的树的各结点度数之和为n-1

(   )6、霍夫曼树一定是满二叉树。

(   )7、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。 

(   )8、在有向图G中，所有结点的出度之和一定等于所有结点的出度之和

(   )9、顺序查找法与折半查找法对存储结构的要求是：顺序查找与折半查找既适用于顺序表，也适用于链表

(   )10、散列表中碰撞的可能性大小与负载因子有关

(   )11. 记录是数据处理的最小单位。 

(   )12. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。 

(   )13. 栈和队列是一种非线性数据结构。  

(   )14．若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列1,5,4,6,2,3。

(   )15. 从逻辑结构上看，n维数组的每个元素均属于n个向量。

(   )16. 稀疏矩阵压缩存储后，必会失去随机存取功能。

(   )17.二叉树中每个结点的两棵子树的高度差等于1。  

(   )18．强连通图的各顶点间均可达。

(   )19．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。

(   )20．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。

    1、 设n为正整数，给出下列程序段的时间复杂度。

void func(int n)

{ int k;

k=1;

while (k  k=k*3;

}

2、列出先序遍历能得到ABC序列的所有不同的二叉树。

3、已知某算法如下，试说明该算法实现的功能。

  #define Max 100

  void unknow(int num ,int r)

   {int st[Max],top=0;

    while (num!=0) {

       st[top++]=num%r;

       num=num/r;

       }

while (top>0)

cout << st[--top] << “ “;

cout << endl;

  }

4、G是一个非连通无向图，共有2边，

则该图至少有多少个顶点？ 

5、 对于下图所示的有向图G，给出从顶点0到其余各顶点的最短路径及路径长度。

6 已知某二叉树先序遍历的结果为：ABDGECFH，其中序遍历的结果为：DGBEAHFC，试画出这棵二叉树。

将一个带头结点的单链表A分解成两个具有相同结构的链表B，C。其中B表的结点是A表中值小于0的结点，而C表的结点为A表中值大于等于0的结点（链表A的元素类型为整形，要求B、C表利用A表的结点。） 

2、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。若用0～7的二进制进行编码，问，对于上述两种编码方案，试比较其优缺点。

7 对关键字序列（7，4，1，14，100，30，5，9，20，134），设哈希函数为h(k)=k % 13,试给出表长为13的哈希表（用线性探测开放定址法处理冲突），并求出在等概率情况下，查找成功的平均查找长度。

1． 在顺序队列中如何解决“假溢出”问题？ 

2． 已知关键字集合（12，2，16，30，8，28，4，10，20，6，18），用快速排序从小到大排序（选第一个记录为基准进行划分），写出第一趟排序结束时的序列。

3． 已知如图1所示的有向图，请给出该图的

(1) 每个顶点的入/出度； (2) 邻接矩阵；

(3) 邻接表；    

4． 假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树边的集合为：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b), (g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树。

5． 将关键字序列（3，26，12，61，38，40，97，75,53，87）调整为大根堆。

6． 已知权值集合为{5，7，2，3，6，9}，要求给出哈夫曼树，并计算其带权路径长度WPL。

7． 有哪四类基本数据结构？ 

8． 使用折半查找的两个前提条件是什么？ 

9． 在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？ 

10． 某二叉树的结点数据采用顺序存储表示如下：

（2）将此二叉树看作森林的二叉树表示，试将它还原为森林。

11． 设散列表的长度为11，散列函数为H(k)=k%11，给定的关键码序列为56,74,23,11,69, 22,59,29。试画出用线性探查法解决冲突时所构成的散列表。

对图1所示带权无向图采用prim算法，从顶点①开始构造最小生成树。（写出加入生成树顶点集合S和选择边Edge的顺序）

1． 将一个带头结点的单链表A分解成两个具有相同结构的链表B，C。其中B表的结点是A表中值小于0的结点，而C表的结点为A表中值大于等于0的结点（链表A的元素类型为整形，要求B、C表利用A表的结点。）求二叉树中叶子结点的数目的递归算法。

3. list指向带头结点的非空线性链表，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。

4. 已知二叉树采用二叉链表存储，试编写一个算法，计算二叉树中叶子结点的个数。

5写出求二叉树深度的算法。 

6．已知11个元素的有序表为（05,13,19,21,37,56,,75,80,88,92）, 请写出折半查找的算法程序，查找关键字为key的数据元素。