电大数据结构本期末综合练习二

1、数据结构（本）期末综合练习二、单项选择题1从 n 个数中选取最大元素（）。A .基本操作是数据元素间的交换C.算法的时间复杂度是0（ n2）2. 线性表采用链式存储时，其地址（A .一定是不连续的C.部分地址必须是连续的3 .设head为非空的单向循环链表头指针， 的值为真。A . p->next=NULLC. p->next=headB .算法的时间复杂度是 0（n）D .需要进行（n +1）次数据元素间的比较）。B 必须是连续的D.可以连续也可以不连续p 指向链表的尾结点， 则满足逻辑表达式 （）B . p->next= =headD . p= =NULL4. 带头结点的

2、单向链表的头指针为A. head = = NULLhead，该链表为空的判定条件是（B. head->next= =headC. head = =head->next5. 设顺序存储的线性表长度为移动元素的次数为 3D . head->next= = NULLn,要删除第i个元素，按课本的算法，当）的值为真。i=（）时,A. 3B. n/26.设顺序存储的线性表长度为C . n-3D . 3n,对于插入操作，设插入位置是等概率的，则插入一个A . 7, 6 , 8, 5C. 7, 6, 5, 89. 设有一个带头结点的链队列,B. 5, 8, 6, 7D. 8, 7, 6,

3、5队列中每个结点由一个数据域data 和指针域 next 组成,元素平均移动元素的次数为（）。A. nB.n/2C. n-1D. n-i+17.一个栈的进栈序列是a, b,c, d,则栈的不可能的出栈序列是（）。A . dcbaB. bcadC. cbadD . adbc8.一个栈的进栈序列是5, 6,7, 8,则栈的不可能的出栈序列是（）（进出栈操作可以交替进行）front 和 rear 分别为链队列的头指针和尾指针,要执行出队操作,用 x 保存出队元素 的值, p 为指向结点类型的指针,可执行如下操作： p=front->next;x=p->data; 然后指行（ ）。A .

4、front=p->next; C. front=p;10. 栈和队列的相同点是（A .都是后进先出C.逻辑结构与线性表不同B. front->next =p;D . front->next=p->next; ）。B .都是后进后出D 逻辑结构与线性表相同，都是操作规则受到限制的线性表11在C语言中，存储字符串“ ABCD ”需要占用（）字节。A. 4B. 2C. 5D. 312.在C语言中，利用数组 a存放字符串“ Hello ”，以下语句中正确的是（）。A. char a10=“Hello” ;B. char a10; a=“Hello” ;C. char a10=

5、Hello 'D. char a10= H'','''0'13 .设有一个10阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储 到一维数组b中。（矩阵A的第一个元素为a“，数组b的下标从1开始），则矩阵 元素a5,3对应一维数组b的数组元素是（）。A. b18B. b8C. b13D. b1014 .设有一个15阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储 到一维数组b中。（矩阵A的第一个元素为a1,1，数组b的下标从1开始），则数组元 素b13对应A的矩阵元素是（）。A. a5,3B .a6,4C .a7

6、,2D .a6,815.深度为5的完全二叉树共有 20个结点，则第5层上有（）个结点（根所在结点为第一-层）。A . 3B. 8C . 5D. 616.一棵完全二叉树共有 30个结点，则该树一共有（）层（根结点所在层为第一层）A . 6B. 4C . 3D . 517.已知一个图的所有顶点的度数之和为m,且m是以下4中情况之一，贝U m只可能是（）。A . 9B. 7C . 15D . 818.以下说法正确的是（）。A .连通图G的生成树中不一定包含G的所有顶点B. 连通图G的生成树中一定要包含G的所有边C. 连通图G 一定存在生成树D. 连通图G的生成树一定是唯一的19.线性表只要以（A .

7、链接对二叉排序树进行A .按层次20.）方式存储就能进行折半查找。B .顺序C .关键字有序的顺序D .二叉树）遍历，遍历所得到的序列是有序序列。B .前序C .中序21 .对n个元素进行冒泡排序若某趟冒泡中只进行了（ 明序列已经排好序。D .后序）次元素间的交换，则表A . 1B . 2C. 0D. n-122. 以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的交换的算法是（）。A .冒泡B .直接选择C.直接插入D .折半插入23. 在对一组元素（64, 48, 106, 33, 25, 82, 70, 55, 93）进行直接插入排序时，当 进行到要把第7个元素70

8、插入到已经排好序的子表时，为找到插入位置，需进行（）次元素间的比较（指由小到大排序）。C. 3A. 624. 对长度为n的线性表进行顺序查找，在等概率情况下，平均查找长度为（A. n25. 如图，若从顶点（B. （n+1） /2C. 2nD. n-1a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为A .acebdgfB .acfedgbC .abecdgfD .abecfdg）。26 .如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为(）。A.acfgedbB.aedcbgfC.acfebdgD.aecbdgf27 棵哈夫曼树有10个非叶子结点（非终端结点），该树总共有

9、（）个结点。A. 21B. 20C. 22D. 1928.棵哈夫曼树有12个叶子结点（终端结点），该树总共有（）个结点。A.21B . 22C. 23D . 2429.队列的插入操作在（）进行。A.队头B .队尾C.队头或队尾D.在任意指疋位置30.队列的删除操作在（）进行。A.队尾B.队头C.队头或队尾D.在任意指疋位置二、填空题1通常可以把某城市中各公交站点间的线路图抽象成 结构。2结构中的元素之间存在多对多的关系称为 结构。3要在一个单向链表中删除 p所指向的结点，已知q指向p所指结点的直接前驱结点， 若链表中结点的指针域为next，则可执行_ _一。4. 设有一个单向循环链表，结点的指

10、针域为next，头指针为head,指针p指向表中某结点，若逻辑表达式 的结果为真，则 p所指结点为尾结点。5. 设有一个链栈，栈顶指针为hs,现有一个s所指向的结点要入栈，则可执行操作禾廿 hs=s;6. 设有一个链栈，栈顶指针为hs,现有一个s所指向的结点要入栈，则可执行操作s->n ext=hs;。7 .在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域为data,指针域为next，若要进行出队操作，并用变量 x存放出队元素的数据值，则相关操作 为一; _。&在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next, s指向一个要入队的结点，则

11、入队操作为 ;9顺序存储字符串“ ABCD ”需要占用 个字节。10.循环队列的最大存储空间为MaxSize=6，采用少用一个元素空间以有效地判断栈空或栈满，若队头指针front=4 ,当队尾指针rear= _时队满，队列中共有 个元素。11. 一棵二叉树叶结点（终端结点）数为 5,单分支结点数为 2,该树共有个结 占八、12. 程序段 char *s= "aBcD ”n=0;while（*s!= '0' if（*s> = 'a'&&*s< = 'z'） n+;s+;执行后n=13. 设一棵完全二叉树，其最高

12、层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10,该完全二叉树一共有 个结点。14. 一棵二叉树中顺序编号为5的结点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在左孩子，则左孩子的编号为 。15. 结构中的数据元素存在一对多的关系称为 结构。16. 根据搜索方法的不同，图的遍历有两种方法。17. 结构中的数据元素存在一对一的关系称为 结构。18. 结构中的数据元素存在多对多的关系称为 结构。19. 如图所示的二叉树，其后序遍历序列为 。20. 一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有 个结点。21. 图的深度优先搜索和广度优先

13、搜索序列不一定是唯一的。此断言是 的。（回答正确或不正确）22. 串的两种最基本的存储方式分别是_和_ _ 。23. 按某关键字对记录序列排序，若关键字 的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。24. 按某关键字对记录序列排序，若关键字 的记录在排序前和排序后 仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题1（1）一组记录的关键字序列为 45，40，65，43，35，95 写出利用快速排序的方法， 以第一个记录为基准得到的一趟划分的结果（要求给出一趟划分中每次扫描和 交换的结果）（2）同样对序列 45 ，40，65，43，35，95

14、利用直接插入排序，写出逐次插入过程 （从第一个元素一直到第六个元素） 。2. 设有一个不带头结点的单向链表，头指针为head，结点类型为NODE，每个结点包含一个数据域data和一个指针域next，该链表有两个结点，p指向第二个结点（尾 结点），按以下要求写出相应语句（不要求完整程序，（ 1）、（ 2）、（ 3）、（ 4）是一个连续的过程） 。（1新开辟一个结点，使指针s指向该结点，结点的数据成员data赋值为1（2）把该结点插入链表的尾部，释放指针s的指向（ 3）删除链表的第一个结点（4）已知pi指向另一个新结点，把它插入到p所指结点和尾结点之间3. （ 1）利用筛选过程把序列 42 ， 8

15、2， 67， 102， 16， 32， 57， 52 建成堆（小根堆） ， 画出相应的完全二叉树（不要求中间过程）（ 2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列4（1）设有序列 10，12，15，19，22，25，100，130，150，200 画出对上述序列进 行折半查找的判定树（以序列中的元素作为树的结点）（2）为了成功查找到 100 需要进行多少次元素间的比较？为了查找9，经过多少次元素间的比较可知道查找失败？5（1）设有一个整数序列 50，38，16，82，110，13，64 ，依次取出序列中的数，构 造一棵二叉排序树（ 2）利用上述二叉排序树，为了查找110，经多少次元素

16、间的比较能成功查到，为了查找 15，经多少次元素间的比较可知道查找失败6（1）设有查找表 5,14,2,6,18,7,4,16,3, 依次取表中数据，构造一棵二叉排序树。（ 2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。四、程序填空题1 以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针struct node ElemType data;struct node *n ext;；struct node *top ;void Push(ElemType x)struct node *p;p=(struct no de*)malloc(1)

17、;p->data=x;(2);(3);2设线性表为(6，10，16, 4)，以下程序用说明结构变量的方法建立单向链表，并输 出链表中各结点中的数据。#define NULL 0void mai n()NODE a,b,c,d,*head,*p;a. data=6;b. data=10;c. data=16;d. data=4; /*d 是尾结点 */head= (1);a. n ext=&b;b. n ext=&c;c. n ext=&d;(2); /*以上结束建表过程*/p=head; /*p为工作指针，准备输出链表*/doprintf( %dn”,);(4);

18、while(5);3. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点，struct node int data;struct node *n ext;；typedef struct n ode NODEint delete(NODE *head,i nt i )NODE *p,*q;int j;q=head;j=0;while(q!=NULL )&&( _(1)(2);j+；if(q=NULL)return(O);p= (3);(4)=p->n ext;free(_);return(1);4. 以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部

19、分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。void In order (struct BTreeNode *BT) if(BT!=NULL)(1) ;(2) ;(3) ;答案一、单项选择题(每小题 2分，共30分)1 . B 2 . D3 . B 4 .D5 .C 6 .B7 .D8 .B 9. D 10 .D11.C12 . A 13 . C14 . A 15. C16. D 17.D 18. C19. C 20 . C 21. C22.B23 . C 24 .B 25 . C26. A27.A28 .C29. B 30 . B二、填空题(

20、每题 2分，共24 分)1图状2. 图状3. q->next= p->next ;4. p->next= =head;5. s->next=hs;6. hs=s;7. x=f->data; f=f->next;8. r->next=s ; r=s;9. 510. 3; 511. 1112. 213. 2114. 1015. 树形16. 深度优先；广度优先17. 线性18. 图状（网状）19. gdbeihfca20. 2n-121 .正确22 .顺序存储链式存储23. 关键字相等的记录24. 关键字相等的记录三、综合应用题1.(1) 45 40 65 43 359535 40 65 43 35