数据结构-复习资料.doc

数据结构-复习资料
1. 快速排序在最坏情况下的时间复杂度为（ D ）。
A．O(log2n) B．O(nlog2n) C．O (n) D. O (n2)
2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。
A. 2k-1 B. 2k C.2k-1 D. 2k-1
3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。
A. 2i B. 2i C. 2i-1 D. 2i-1
4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。
A. p->next=p->next->next B. p=p->next
C. p=p->next->next D. p->next=p
5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。
A. 6 B. 4 C. 3 D. 2
6.设有以下四种排序方法，则（ B ）的空间复杂度最大。
A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序
7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。
A. 3 B. 4 C. 5 D. 1
8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。
A. 4 B. 5 C. 6 D. 7
9．对一个算法的评价，不包括如下（ A ）方面的内容。
A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度
10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。
A．O(1) B．O(n) C．O(log2n) D．O(n2)
11. 队列是一种（ B ）的线性表。
A．先进后出 B．先进先出 C．只能插入 D．只能删除
12．采用开放定址法处理散列表的冲突时，其平均查找长度（ C ）。
A．低于链接法处理冲突 B. 及链接法处理冲突相同
C．高于链接法处理冲突 D．高于二分查找
13.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ A ）。
A. log2n+1 B．log2n-1 C. log2n D. log2(n+1)
14. 从数据结构上讲，字符串是比较特殊的（ C ）。
A．堆栈 B． 队列 C．线性表 D．二叉树
15．函数substring(“DATASTRUCTURE”，5，9)的返回值为（ A ）。
A．STRUCTURE B．DATA
C．ASTRUCTUR D．DATASTRUCTURE
16．队列是一种（ B ）的线性表。
A．先进后出 B．先进先出 C．只能插入 D．只能删除
17．对一个算法的评价，不包括如下（ A ）方面的内容。
A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度
18. 从二叉搜索树中查找一个元素时，其时间复杂度大致为（ C ）。
A. O(n) B. O(1) C. O(log2n) D. O(n2)
19．采用开放定址法处理散列表的冲突时，其平均查找长度（ C ）。
A．低于链接法处理冲突 B. 及链接法处理冲突相同
C．高于链接法处理冲突 D．高于二分查找
20.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ A ）。
A. log2n+1 B．log2n-1 C. log2n D. log2(n+1)
21．下列四种排序中（ D ）的空间复杂度最大。
A.堆 B．冒泡排序 C.希尔排序 D.快速排序
22．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ B ）。
A. N0=N1+1 B． N0=N2+1 C. N0=Nl+N2 D. N0=2N1+l
23．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ B ）。
A. 冒泡排序 B.堆排序 C.希尔排序 D.快速排序

1．字符串必须以字符’\0’表示串值的终结。√
2．哈夫曼树中没有度数为1的结点。√
3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。√
4．设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。
5．分块查找的平均查找长度不仅及索引表的长度有关，而且及块的长度有关。√
6．如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。√
7．有向图的邻接表和逆邻接表中表结点的个数不一定相等。
8．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。√
9．线性表中的所有元素都有一个前驱元素和后继元素。
10．带权无向图的最小生成树是唯一的。
11. 线性表中的所有元素都有一个前驱元素和后继元素。
12.  非空的双向循环链表中任何结点的前驱指针均不为空。√
13．图的邻接矩阵法：n个顶点需要n*n个单元存储边(弧)；空间效率为O(n2)。√
14．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
15．入栈操作和入队列操作在链式存储结构上实现时需要考虑栈溢出的情况。
16．中序遍历一棵二叉排序树可以得到一个有序的序列。√
17．顺序表查找指的是在顺序存储结构上进行查找。

1．设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; p->next = s; ;。

2. 具有n个顶点， __ n（n－1）/2___条边的图，称为完全无向图；具有n个顶点， ____ n(n-1)____条弧的有向图，称为完全有向图。
3. 设输入序列为1、2、3，则经过栈的作用后可以得到____5____种不同的输出序列。
4. 设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_ p->lchild==0&&p->rchild==0 ___。
5. 设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_ p->lchild==0&&p->rchild==0________。
6. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为__19,18,16,20,30,22____________________________。
7. for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_____ O(n) ____。
8. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____i/2________，右孩子结点的编号为____ 2i+1 _______。
9. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_2d______。
10. 设有向图G的二元组形式表示为G =（V，E），V={1，2，3，4，5}，E={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则该图的一种拓扑排序序列为___1,3,2,4,5_____________________ 。
11. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较___7_____次就可以断定数据元素X是否在查找表中。
12．设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为________ 49，13，27，50，76，38，65，97 ______________。
13．设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为___BADC_______。
14．完全二叉树中第5层上最少有_____1_____个结点，最多有___16______个结点。
15．设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16及_____50______相互交换即可。
16. 子串的定位运算通常称为串的_串匹配___，是串处理中最重要的运算之一
若n为主串长度，m为子串长度，则串的匹配算法时间复杂度为_m*n___。
17 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_ O(log2n)_______，整个堆排序过程的时间复杂度为_ O(nlog2n)_______。
18. 具有n个顶点， ____ n（n－1）/2_________条边的图，称为完全无向图；具有n个顶点， ____ n(n-1)____________条弧的有向图，称为完全有向图。
19 一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，查找关键字62时的比较次数为___2____，查找成功时的平均查找长度_ ASL=91*1+2*2+3*4+4*2)=25/9___。
20．设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16及____50_______相互交换即可。

1．阅读下面的算法
LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L; L=L－>next; p=L;
S1: while(p－>next) p=p－>next;
p－>next=q; q－>next=NULL;}
return L;}
请回答下列问题：
1） 说明语句S1的功能；
答：查询链表的尾结点
2）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表________（a2,a3,……,an,a1）_______________________。

2. 阅读下面算法：
  void ABC(BTNode * BT) {
if （BT） {
ABC (BT->left);
cout<<BT->data<<’’;
ABC (BT->right);
}
}
该算法的功能是：____递归地后序遍历链式存储的二叉树。____________。

3．阅读下面算法
void conversion(){
Stack s; int n; SElemType e; initstack(s);
printf("Please input number:");
scanf(“%d”,&n);
while(n){
push(s,n%6); n=n/6;
}
while(!stackempty(s)){
pop(s,e); printf(“%d”,e);
}}
1) 指出该算法的功能。
答：十进制转六进制
2) 若输入数据为10，则输出结果为____14_____________。

4. 阅读下列函数
int arrange(int a[], int 1, int h, int x) {
//1和h分别为数据区的下界和上界
int i,j,t；
i=1；j=h；
while(i<j){
while(i<j && a[j]>=x)j--；
while(i<j && a[j]>=x)i++；
if(i<j){
t=a[j]；a[j]=a[i]；a[i]=t；
}}
if(a[i]<x) return i；
else return i－1；}
指出该算法的功能是。
答：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x 的元素均落在a[i＋1..h]上。

5. 阅读下列算法
void quickpass(int r[], int s, int t){
int i=s,j=t,x=r[s];
while(i<j){
while (i<j && r[j]%2==0) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}
while (i<j && r[i]%2==1) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}
}
r[i]=x;}
指出该算法的功能。
答：所有奇数移到所有偶数之前
6. 阅读下面算法：
void myMethod(List *L)
{ int m,i,j,flag=1;
RecordType x;
m=n-1;
while((m>0)&&(flag==1))
{ flag=0;
for(j=1;j<=m;j++)
if(L->r[j].key>L->r[j+1].key)
{ flag=1;
x=L->r[j]; L->r[j]=L->r[j+1]; L->r[j+1]=x;
}
m--;
}
}该算法的功能是：___冒泡排序_______________________。

7. 阅读下列算法
int arrange(int a[], int 1, int h, int x) {
int i,j,t； i=1；j=h；//1和h分别为数据区的下界和上界
while(i<j){
while(i<j && a[j]>=x)j--；
while(i<j && a[j]>=x)i++；
if(i<j){ t=a[j]；a[j]=a[i]；a[i]=t；}}
if(a[i]<x) return i；
else return i－1；}
指出该算法的功能。
答: 调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x 的元素均落在a[i＋1..h]上。
8. 阅读下列算法
typedef int datatype;
typedef struct node {datatype data; struct node *next;}lklist;
void delredundant(lklist *&head){
lklist *p,*q,*s;
for(p=head;p!=0;p=p->next){
for(q=p->next,s=q;q!=0; )
if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}
else {s=q,q=q->next;}}}
指出该算法的功能。
答：在单链表中删除值相同的多余结点
9. 阅读以下二叉树操作算法，指出该算法的功能。
Template <calss type > void BinTree <Type> ：：
unknown(BinTreeNode<Type> *t) {
BinTreeNode<Type> *p = t, *temp;
if (p!=NULL) {
temp = p→leftchild;
p→leftchild = p→rightchild;
p→rightchild = temp;
unknown(p→leftchild);
unknown(p→rightchild);
}
}
该算法的功能是：_________左右子树交换________________________。

1.用克鲁斯卡尔算法分析下列无向网，画出最小生成树。
2．已知一个图G的顶点集V各边集E，当它用邻接矩阵或邻接表表示时，分析按深度优先和广度优先搜索遍历得到的顶点序列。
3.散列表为HT，散列函数为H（key）= key % d，用线性探查法解决冲突，求散列表。
4. 用prim算法画出下图的最小生成树（假设从V1开始计算）。
V1

V3

V7

V2

V4

V5

V6

45

42

52

65

50

60

50

40

30

70

编写程序。
12 / 12