《算法与数据结构》复习纲要B一、单选题1.数据结构中的数据和存贮介质（如磁盘）的关系是（）0A.数据是存贮介质B.存贮介质是数据的载体C.存贮介质是传送数据的工具D.数据是计算机处理对象，存贮介质是磁盘2.字符串abed |与字符串|abcde| 比较后的关系是（A.“abed” > “abede”B."abed” < "abede”C.“abed” <= “abede”D.“abed” >= “abede”3.子串"jing"在主串Z/Beijing&Nanjing&Shanghai/z中的位置是（）。
A. 4B. 3C. 4, 13D. 134.在树中，树的度与结点的度之间的关系是（）oA.树的度就是结点的度B.树的度为2,结点的度可以是0, 1和2C.结点度中最大值为树的度D.树的度与结点的度无关5.—•个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。
如果按层次顺序从1开始对全部结点编号，问各层的结点数是多少？()A.第i层的结点数2i-lB.第i层的结点数KiTB.第i层的结点数是K D.第i层的结点数是1+2+3+…+K6.设n为止整数。
试确定下列程序段屮带标号@的语句的频度()。
For(i=l;i〈=n;i++)For(j=l;j<=i;j++)For(k=l;k<=j;k++)@x=x+delta;A.l+(l+2) + (1+2+3)+・・・ + (1+2+3+.・・ +n)B.n*i*jC.n*n*nD.1+2+3+.. . +n)7.在一个双向链表中，假设结点的域分别为left, right以及data。
其中left, right 分别为两个链域，data是数据域。
下一段程序是实现在h结点之后插入p结点的功能，其中h结点不空，h的下一个结点亦不空。
()程序是正确的。
A.p->right = h~>right; p->left = h; h->right = p; p->right->right = p;B.p->right = h~>right; p->]eft = h; h->right 二p; p->right->left = p;C.h~>right = p; p->left = h; p->right = h->ri ght; p->right->left = p;D.p->right = h->right; p->left = h; h->right = p; h->right->lef t = p;8. 设n 为正桀数。
下列程序段中带标号@的语句的频度是（）。
X=91; Y=100; While(y>0)@If(x>100){ X 二x - 10;Y=y - 1：} el se x=x+l; A.无穷多次 B. 1100C. 9100【)• 100二、多选题1. 常用的堆栈存贮结构有（）。
A.顺序存贮结构C.顺序存贮与链表存贮混合结构 2. 图的邻接矩阵存贮结构包括（）。
A.表示图中顶点间相邻关系的矩阵 C.表示图屮顶点元素的数组 E. 表示出度的数组3. 下述陈述中哪一项是正确的？（）A.文件是由记录组成的集合 C.文件是由数据项组成的4. 下列排序算法中哪些是不稳定的？（A.冒泡排序 C.快速排序5. 假设以琏表的方式实现堆栈，top 为栈顶指针，指向类型为1 inkstack 类型，下述程序 实现将堆栈初始化为空栈的操作。
（）程序是止确的。
A. void INTTSTACK( linkstack *top ) {top = NULL;};B. void INlTSTACK(linkstack * top ) {top = —1；}；C. void INITSTACK(1 inkstack * top ) {top = 0;};D. void INITSTACK(linkstack * top ) {top 二空;};B.链表存贮结构 D.指针存贮结构B.对称矩阵 D.表示入度的数组 B.记录是文件存取的基本单位 D.数据项有吋也被称Z 为字段 B.选择排序 I ）.堆排序6.假设以链农的方式实现堆栈,top为栈顶指针,类型为1 inkstack结点分别以data和next 表示数据域与链域，datatype表示栈内元素的数据类型。
下述程序实现出栈操作中() 程序是错误的。
A.datatype pop( linkstack *top ){ linkstack * p ;if ( top 二二NULL ){ ERROR( u underflow");Return NULL;else{ p = top; top = top->next; x = p->data; free(p); return x; };B.datatype pop( 1i nkstack *top ){ linkstack * p ; p 二top； top = top->next; x = p->data; free(p) ; return x; };C.datatype pop( linkstack *top ){ linkstack * p ;if ( top = NULL ){ERROR( “underflow” );Return NULL; }el se{ p = top; top = top->next; return p->data;};D.voi d pop ( 1 inkstack *top ){ linkstack * p ;if ( top = NULL ){ ERROR( “underflow” );Return NULL;}else{ p = top; top = top->next; x = p->data;}三、填空题1.数据对象的结构分____________ 和非线性结构二种。
2.算法的五个重要特性分別是：有穷性，_____________ ,可行性，有输入，有输出。
3.具有____________ n (n>二0)个元素构成的有限序列称为线性农。
4.列举任意2个线性农的操作：____________ o5.在数组a屮存贮有线性表，数组长度为n,下述算法是删除第1个元素的算法，请在横线上填充代码，完善程序。
void DELETELTST(char line [ ], int n, int i){ if (i-l<0 || i-l>n-l)printf ( 'The position is not exist!');else {for (j=i; j>=n-l ; j++)n 二nT;}6.列举三个或三个以上的队列的操作：____________ 、出队、_____________ o7. _________________________ 图的遍历分为和广度优先遍历。
&衡量内部排序算法的指标有关键字比较次数、 ______________ 移动次数以及算法所需要的四、判断题1.栈满是数据对象栈的固有操作。
（）2.空串是打印后不出现任何字符的字符器。
（）3.度为二的树是二叉树。
（）4.二叉树是一种特殊的图。
（）5.拓扑排序是图的另一•种遍历。
（）6.-棵度为2的树是一•棵二叉树。
（）7.分块查找吋引入了静态查找就是顺序查找、折半查找和分块查找。
（）8.动态杳找的概念是指杳找中指定关键字不断发牛变化的查找。
（）9.快速排序是稳定的。
（）10.线性结构中，每个点至多有一个前趋和一个片继，树中一个结点至多有一个前趋和多个后继，图中的结点可以有多个前趋利多个后继。
（）五、简答丿1.描述数据对象物理结构与逻辑结构的概念。
2.简述数据的概念。
3.简要描述信息的概念。
4.写出建立单向链表的算法。
5.两个串相等的充分必要条件是什么？《算法与数据结构》复习纲要B答案一、单项选择题题号 1 2 3 4 5 6 7 8答案 B B A C B A B B二、多项选择题题号 1 2 3 4 5 6答案AB AC BD BCD AC BCD三、填空（1）线性结构（2）确定性（3）相同特性的5（4）初始化求线性表长度取线性表第I个元素；在线性表第I个元素后插入一个值为x的元素删除线性表中第I个元素；（任选两个答案答对都得满分）（5）line[j]=line|j+lj （6）入队，队空判断（7）深度优先遍历（8）记录，空间四、判断题题号 1 2 3 4 5 6 7 8 9 10 答案 F F F T T F F F F T五、简答题1逻辑结构是数据对彖固有的、表示数据及其彼此Z间的关系，物理结构是数据对彖的元素及其关系在计算机内的存贮方法。
2数据指所有能输入计算机中，并被计算机程序处理的符号的总称3信息是经过计算机加工处理的带有一定意义的结果。
4 struct node { char data;struct node * link;Void CreateLinkList() {list=NULL;for (i = 1; i < n; i++ ) {ch=getchar();p=(struct node *)malloc(sizeof(struct node));p->data=ch; p->link=Null;p->link = list; list = p;}5两个串相等的充分必要条件是两个串中的元索及其顺序均一样。
〃创建一个空链表〃 〃取一个数据元素〃〃申请一个新结。
