2.(1) low<=high (2) mid;
(3) a[mid].key (5) 不能，因为不是有序序列，不能用折半查找 3． （1）j<=n-1 （2）i<=n-j （3）a[i]=a[i+1] （4）a[i+1]=temp （5）4,5,2,1,6,8 4. （1） Inorder(BT->left) （2） printf(“%c”,BT->data) （3）f,d,e,b,c,a 练习三 一、单项选择题 1.对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73 个零元素，其相应的三元组表共有( )个元素。 A．8 B．80 C．7 D．10 2. 对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73 个零元素，A的右下角元素为6，其相应的三元组表中的第7个元素是( )。 A．（10，8，6） B．（10，8，7） C．（7，10，8） D．（7，8，10 ） 3.字符串( )是“abcd321ABCD”的子串。 A. “21AB” B. “abcD” C. “aBCD” D. “321a” 4. 字符串 a1=〝CDEIJING〞, a2 =〝CDEI〞 , a3= 〝CDEFANG〞 a4=〝CDEFI〞 中最大的是（ ）。 A. a4 B. a2 C. a3 D.a1 5.栈和队列的共同特点是（ ）。 A．都是操作受限的线性结构 B．元素都可以随机进出 第21页 C．都是先进后出 D．都是先进先出 6. 序列12,8,4,3按顺序依次进栈，该队列的不可能输出序列是（ ）。 (进栈出栈可以交替进行）。 A．8,12,3,4 B．12,8,4,3 C．3,4,8,12 D．3,4,12,8 7. 在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点,要为结点p 所指结点赋值x,并入队的运算为p->data=x; p->next=NULL;（ ）。 A. f->next=p; f=p; B． r->next=p;r=p; C． r=p; p->next=r; D． p->next=f;f=p; 8. 对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点,并给该 结点赋值a,则执行: p=(struct node *)malloc(sizeof(struct node);p->data=a; 和( ）。 A. p->nex=top; top=p; B．top->next=p; p=top; C．top=top->next; pe=top; D．p->next=top; p=top; 9. 数据结构中，与所使用的计算机无关的是数据的( ) 结构。 A.逻辑 B.存储 C.逻辑与存储 D.物理 10. 数据的存储结构包括数据元素的表示和（ ） A . 数据处理的方法 B.相关算法 C . 数据元素间的关系的表示 D. 数据元素的类型 11．顺序表所具备的特点之一是（ ）。 A．可以随机访问任一结点 B．不需要占用连续的存储空间 C．插入元素的操作不需要移动元素 D．删除元素的操作不需要移动元素 12. 头指针为head的带头结点的单向链表为空的判定条件是( )为真。 A. head= =NULL B. head->next!=NULL C. head->next= =NULL D. head->next!= NULL 13. 数据元素是数据的基本单位，它（ ）。 A．只能有一个数据项组成 B．至少有二个数据项组成 C．可以是一个数据项也可以由若干个数据项组成 D．至少有一个数据项为指针类型 14 .下面关于线性表的叙述中,错误的是( )。 A. 线性表采用顺序存储,必须占用一片连续的存储空间 B. 线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动 C. 线性表采用链式存储，不必占用连续的存储空间 D. 线性表采用链式存储，进行插入删除操作，不需要移动元素 15．设有头指针为head的非空的单向链表, 指针p指向其尾结点, 要使该单向链表成为单向循环链表,则可利用下述语句（ ）。 A．p =head; B．p=NULL; C．p->next =head; D．head=p; 16．在一个头指针为head的单向循环链表中，p指向尾结点，要使该链表成为单向链表 可执行（ ）。 A．p=NULL; B． P->next=head; C．head->next=p->next ; D． p->next=NULL; 17. 在线性表的顺序结构中，以下说法正确的是（ ）。 第22页 A．逻辑上相邻的元素在物理位置上不一定相邻 B．数据元素是不能随机访问的 C．逻辑上相邻的元素在物理位置上也相邻 D．进行数据元素的插入、删除效率较高 18. 子串“acd”在主串 “abdcacdefac”中的位置是 （ ) 。 A．3 B．1 C．5 D．7 19.对链表, 以下叙述中正确的是（ ）。 A．不能随机访问任一结点 B．结点占用的存储空间是连续的 C．插入删除元素的操作一定要要移动结点 D．可以通过下标对链表进行直接访问 20．设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一 维数组B中（数组下标从1开始），B数组共有55个元素,则该矩阵是（ ）阶的 对称矩阵。 A．5 B．20 C．10 D．15 21 .设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素 作为新表的第5个元素），则移动元素个数为（ ）。 A．30 B．31 C. 5 D．6 22.设有一个长度为15的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（ ）。 A．10 B．11 C. 5 D．6 23．设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数 为（ ）。 A．11 B．10 C．30 D．31 24．设有一个长度为26的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为 （ ）。 A．9 B．10 C．15 D．16 25．设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组B中（数组下标从1开始），则矩阵中元素 a7,5在一维数组B中的下标是 （ ）。 A．25 B．24 C．26 D．27 26．设有一个38阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组B中（数组下标从1开始），则矩阵中元素53在一维数组B中的下标 是（ ）。 A．a9,7, B．a10,8 C．a10,7 D．a9,8 27．线性表在存储后,如果相关操作中有要求:利用已知的指向某结点的指针或序号,访问 该结点的前驱结点，则采用（ ）的存储方式是不可行的。 A．单向链表 B．双向链表 C．单向循环链表 D．顺序表 28. 设单向链表中,指针p指向结点A，q为指向结点类型的指针变量，若要删除A的直接 后继，则所需修改指针的操作为 q=p->next; 和 ( ) 。 A.p->next=q->next; C.p=p->next; B.p=q->next; D.p->next=q; 第23页 29．在一棵二叉树中，若编号为i的结点存在左孩子,i结点的左孩子的顺序编号为（ ）。 A．i/2.0 B．2*i C．2*i+1 D．i+2 30．在一棵二叉树中，若编号为7的结点存在右孩子,他的右孩子的顺序编号为（ ）。 A．8 B．9 C．14 D．15 二、填空题 1. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是________。 2. 树形结构和_______都属非线性结构。 3. 数据结构中，数据元素之间的抽象关系称为________结构 4. 结构中的数据元素存在一对一的关系称为________结构。 5. 栈的操作特点是后进________ 。 6. 循环队列的最大存储空间为MaxSize,若队头指针front，队尾指针rear, ,采用少用一个 存储空间以有效地判断栈空或栈满，队满的判定条件为________ 。 7. 广义表(( b,a,c) ,c ,d , f , e ,( (i , j ) , k ) ) 的表头是________。 8. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的深度是________。 9. 设有一个长度为18的顺序表 , 第8号元素到第18号元素依次存放的值为8,9,?,18. 某人想要删除第8号元素，程序中他的做法是用语句for(i=18;i<=9;i--)a[i-1]=a[i]; 即从第18号元素开始, 直到第9号元素,每个元素依次向前(左)移动1个位置.事实上这 样做是错误的.其结果新表中第9号元素的值为________。 10. 求两个n阶矩阵的乘积，算法的基本操作为乘法，时间复杂度为 ________。 11. 一棵二叉树,有1个2度结点,，2个1度结点，则该树共有 _______个结点。 12．一棵有15个结点的二叉树，其1度结点数的个数为2，则该树共有_______个叶结点。 13．设有一棵深度为5的完全二叉树，该树共有21个结点,第5层上有 个结点。 （根所在结点为第1层） 14．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行8列的稀疏矩阵A，其相应的三元 组表共有6个元素,稀疏矩阵A共有_______个零元素。 15．中序遍历________树可得到一个有序序列。 16．一棵有21个叶结点的哈夫曼树，则该树共有_______个结点。 17. 序列12,10,13,11,16,14,采用冒泡排序算法,经一趟冒泡后,序列的结果是________。 （按升序排序） 18. 28个元素进行冒泡法排序，通常第8趟冒泡要进行__ ____次元素间的比较。 19. 对16个元素的序列用冒泡排序法进行排序，共需要进行________趟冒泡。 20.对一组记录（51，35，93，20，12，78，56，41，79）进行直接插入排序(由小到 大排序) ，当把第8个记录41插入有序表，为寻找插入位置需比较________次。 21. 一棵有16个叶结点的哈夫曼树，则该树共有_______个非叶结点。 22.在双向链表中，每个结点有两个指针域，一个指向该结点的直接后继 ，另一个指向 _________。 23. 在对一组记录（40，24，82，9，1，78，46，31，69）进行直接插入排序(由小到大排 序) ，当把第7个记录46插入到有序表时，为寻找插入位置需比较________次。 24．在查找表中，若通过记录的某关键字能唯一地确定一个记录，称该关键字为_________。 三、综合题 1． 设有序表为(5, 8, 14, 15, 33, 51, 61, 73, 81, 82, 93) ,元素的序号依次为 第24页 1,2,3,??，11. （1）画出对上述查找表进行折半查找所对应的判定树（树中结点可用序号表示） （2）说明成功查找到元素33需要经过多少次比较？ (3) 在等概率条件下, 给出成功查找的平均查找长度 2．设有序表为(20, 38, 48, 60, 68, 69, 80) ,元素的序号依次为1,2,3,??，7. （1） 画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示） （2） 说明成功查找到元素20需要经过多少次比较？ (3) 说明不成功查找元素39需要经过多少次比较？ （4） 给出中序遍历该折半查找判定树的序列 3． (1)如图1所示,若从顶点a出发，首先经过c按图的深度优先搜索法进行遍历，给出可能得到的一种顶点序列。 a he c d b f (2)设有向图如图2所示下，写出首先删除顶点1的1种拓扑序列 图1 1 2 3 4 56 图2 4． (1) 以3，4，5，8，9，10作为叶结点的权，构造一棵哈夫曼树 (2) 给出相应权重值叶结点的哈夫曼编码。 5. (1) 设数据集合a={7,4,9,8,6,5,3},依次取a中各数据，构造一棵二叉排序树。 (2)对该二叉树进行查找，成功查找到5要进行多少次元素间的比较？ (3) 给出对上述二叉排序树进行中序遍历的序列 6． (1)如图3所示，若从顶点a出发，首先经过c按深度优先搜索法进行遍历，给出可能得到 第25页