2022年《计算机软件技术基础》试题答案

1、运算机软件技术基础试题1. 线性表的链式储备结构与次序储备结构相比优点是 CD ；A. 全部的操作算法实现简洁B. 便于随机存取C. 便于插入和删除D. 便于利用零散的储备器空间2. 线性表是具有n 个 C 的有限序列；A. 表元素B. 字符C. 数据元素D. 数据项E. 信息项3. 如长度为 n 的线性表采纳次序储备结构,杂度为 C ；（1 I n+1）在其第 I 个位置插入一个新元素的算法的时间复A. O0 B. O12C. On D. On4. 设 A 是一个线性表 a1,a2, ,an,采纳次序储备结构,就在等概率的前提下,平均每插入一个元素需要移动的元素个数为 B ,平均每删除一个元

2、素需要移动的元素个数为 A ；如元素插在 ai 与 ai+1 之间 0 I n-1 的概率为 2 n i ,就平均每插入一个n n 1 元素所要移动的元素个数为 C ；n 1 nA. B. 2 2C. 2n 1 D. 3n 13 45. 以下函数中,按它们在 n 时的无穷大阶数,最大的是 D ；A. log n B. nlog nn/2C. 2 D. n.next nextpsnext6. 将下图所示的s 所指结点加到p 所指的结点之后,其语句应为： D ；A. s-next=p+1; p-next=s;B. *p.next=s; *s.next=*p.next;C. s-next=p-nex

3、t; p-next=s-next;D. s-next=p-next; p-next=s;7. 将两个各有 n 个元素的有序表归并为一个有序表时,其最少的比较次数是 A ；A. n B. 2n-1C. n-1 D. 2n8. 下面的程序段是合并两个无头结点链表 ha 和 hb 为一个无头结点链表 ha 的过程,作为参数的两个链表都是按结点的data 域由大到小链接的；合并后新链表的结点仍按此方式链接；请填写下述空框,使程序能正确运行；1.#define NULL 0 typedef struct node int data; struct node *next; node, linklistty

4、pe; void combinelinklisttype *ha, linklisttype *hb linklisttype *h, *p; h = linklisttype *mallocsizeoflinklisttype; h-next = NULL; p = h;whileha .= NULL & hb .= NULLifha-data=hb-data /* 较大的元素先插入*/p-next = 1 ; p = 2 ; 3 ; else p-next = 4 ; p = 5 ; 6 ; ifha=NULL 7 ; ifhb=NULL 8 ; ha = h-next; freeh; 参

5、考答案：1 ha 2 p-next 3 ha=ha-next 4 hb 5 p-next 6 hb=hb-next 7 p-next=hb 8 p-next=ha 9. 假如表 A 中全部元素 a 1,a 2, ,a n 与表 B 的一个次序子表 b k,b k+1, b k+n-1 完全相同（即 a1=bk,a2=bk+1, an=bk+n-1）,就称表 A 包含在表 B中；设 ha,hb 为带头结点的单链表,分别表示有序表 A和 B,下面的函数用于判别表A 是否包含在表B 中,如是,就返回true ,否就返回 false ；（提示：用递归实现）#define true 1 #define

6、false 0 #define NULL 0 typedef struct nodeint data; struct node *next; node, linklisttype;int inclusionlinklisttype *ha, linklisttype *hb linklisttype *pa, *pb; pa = ha-next;pb = hb-next; 1 ; while 2 ifpa-data=pb-data 3 ; else 4 ; 5 ; 参考答案：1 ifpa=NULL returntrue 2 pb.=NULL & pa-data=pb-data 3 return

7、inclusionpa, pb 4 pb = pb-next; 5 returnfalse 10. 在此题的程序中,函数 create_link_listn 建立一个具有 n 个结点的循环链表；函数 josephusn,I,m 对由 create_link_listn 所建立的具有 n 个结点的循环链表按肯定的次 序逐个输出,并删除链表中的全部结点；参数 nn0 指明循环链表的结点个数,参数 I1I n 指明起始结点,参数m（m0是步长）,指明从起始结点或前次被删除并输出的结点之后的第 m个结点作为本次被输出并删除的结点；例如,对于下图所示的具有 6 个结点的循环链表,在调用 josephus

8、6,3,2 后,将输出 5,1,3,6,4,2；请在空框处填上适当内容,每框只填一个语句；#define NULL 0 typedef struct node int data; struct node *next; node, linklisttype;linklisttype *create_link_listint n linklisttype *head, *p, *q; int I;head = NULL; ifn0 head = linklisttype *mallocsizeoflinklisttype; p = head;forI=1;Idata = I; q = linkli

9、sttype *mallocsizeoflinklistttype; 1 ; 2 ; p-data = n; 3 ; /* 建立从尾链到首的环形结构*/ returnhead; void Josephusint n, int j, int m linklisttype *p, *q; int j;p = create_link_listn; for;I1;I- p = p-next; 4 ; whilejn forI=1;Inext; 5 ; printf“ %8d” ,q -data; 6 ; freeq; j=j+1; 参考答案：1 p-next = q; 2 p = q; 3 p-nex

10、t = head 4 j=0 5 q=p-next; 6 p-next = q-next 11. 在以下程序中, 函数 differenceA,B 用于求两集合之差 C=A-B,即当且仅当 e 是 A 中的 一个元素,且不是 B 中的元素时, e 是 C中的一个元素；集合用有序链表实现,用一个空链 表表示一个空集合,表示非空集合的链表依据元素之值按递增排列,执行 C=A-B之后, 表示集合 A 和 B的链表不变, 如结果集合C非空,就表示它的链表应依据元素之值按递增序排列；函数 append 用于在链表中添加结点；#include #define NULL 0 typedef struct n

11、ode int data; struct node *next; NODE;NODE *appendNODE *last, int x last-next=NODE *mallocsizeofNODE; last-next-data=x; returnlast-next; NODE *differenceNODE *A ,NODE *B NODE *C,*last; C=last=NODE *mallocsizeofNODE; while 1 ifA-data data last=appendlast,A-data; A=A-next; else if 2 A=A-next; B=B-next

12、; else 3 ; while 4 last=appendlast,A-data; A=A-next; 5 ; last=C; C=C-next; freelast; returnC; 参考答案：1 A.=NULL & B.=NULL 2 A-data=B-data 3 B=B-next; 4 A.=NULL 5 last-next=NULL; 12. 阅读以下算法,填充空格,使其成为完整的算法；其功能是在一个非递减的次序储备线 性表中 从下标 1 处开头储备 ,删除全部值相等的余外元素；#define MAXSIZE 30 typedef struct int elemMAXSIZE; 表

13、长 */ int length;/* sqlisttype;void exam21sqlisttype *Lint I,j; I=2,j=1; while 1 ifL-elemIL-elemj 2 ; 3 ; I+; 4 ; 参考答案：1 ilength 2 3 j+; 4 13. 用单链表表示的链式队列的队头在链表的 A 位置；A. 链头 B. 链尾 C. 链中；14. 如用单链表表示队列,就应当选用 B A. 带尾指针的非循环链表 B. 带尾指针的循环链表 C. 带头指针的非循环链表 D. 带头指针的循环链表 15. 在解决运算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区

14、,主 先放入打印 机将要输出的数据依次写入该缓冲区,而打印机就从该缓冲区中取出数据打印,缓冲区的数据先被打印；该缓冲区应当是一个 B 结构；A. 堆栈 B. 队列 C. 数组 D. 线性表 16. 如用一个大小为 6 的数组来实现循环队列,且当前 rear 和 front 的值分别为 0 和 3；当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为 B ；A. 1 和 5 B. 2 和 4C. 4 和 2 D. 5 和 117. 设栈的输入序列为 1,2 , ,10 ,输出序列为 a1,a2, ,a 10,如 a5=10,就 a7 为 C ；A. 4 B. 8 C.不

15、确定18. 设栈的输入序列是 1,2,3,4,就 D 不行能是其出栈序列；A 1243 B. 2134 C. 1432 D. 431219. 以下 D 是 C语言中”abcd321ABCD” 的子串；A. abcd B. 321AB C. “ abcABC”D. “ 21AB”20. 如串 S=” software ” ,其子串的数目是 C ；A. 8 B. 37 C. 36 D. 921. 将一个 A1:100,1:100 的三对角矩阵,按行优先存入一维数组 B1:298 中, A 中元素A66,65 即该元素的下标 在 B 数组中位置 k 为 B ；A. 198 B. 195 C. 197

16、 D. 19622. 设高为 h 的二叉树只有度为 0 和 2 的结点,就此类二叉树的结点数至少为 B ,至多为 F ；高为 h 的完全二叉树的结点数至少为 E ,至多为 F ；A 2h B. 2h-1 C. 2h+1 +1E. 2 F. 2 h-1 G. 2 h+1-1 H. 2 h+1 h-123. 一棵有 124 个叶结点的完全二叉树,最多有 B 个结点；A. 247 B. 248 C. 249 D. 25124. 如从二叉树的任一结点动身到根的路径上所经过的结点序列按其关键字有序,就该二叉树是 C ；A. 满二叉树 B. 哈夫曼树C. 堆 D. 二叉查找树25. 前序遍历和中序遍历结果

17、相同的二叉树为 F ；前序遍历和后序遍历结果相同的二叉树为 B ；A. 一般二叉树 B. 只有根结点的二叉树C. 根结点无左孩子的二叉树 E. 全部结点只有左孩子的二叉树D. 根结点无右孩子的二叉树 F. 全部结点只有右孩子的二叉树26. 具有 n 个结点的完全二叉树,已经次序储备在一维数组 A1.n 中,下面的算法是将 A 中次序储备变为二叉链表储备的完全二叉树；请填写适当语句在下面的空格内,完成上述算 法；#define MAXSIZE 30 typedef struct btnode int data; struct btnode *lchild, *rchild; BTN;void c

18、reatetreeBTN *p,int A, int I,int n 1 ; p-data=AI; if 2 3 ; else p-lchild=NULL; if 4 createtree 5 ; else p-rchild=NULL; void btreeBTN * p ,int A,int n createtreep,A,1,n; 参考答案：1 p=BTN *mallocsizeofBTN 2 2*Ilchild,A,2*I,n 4 2*I+1rchild,A,2*I+1,n27. 如在线性表中采纳折半查找法查找元素,该线性表应当 C ；A. 元素按值有序B. 采纳次序储备结构C. 元素按

19、值有序,且采纳次序储备结构 D. 元素按值有序,且采纳链式储备结构28. 在分块检索中,对 256 个元素的线性表分成 16 块最好,每块的正确长度是 16 ；如每块的长度为 8,其平均检索长度为 21 ；29. 假定有 K 个关键字互为同义词,如用线性探测法把这进行 D 次探测；B. K 次A. K-1次K 个关键字存入散列表中,至少要C. K+1 次 D. KK+1/2 次30. 在 n 个记录的有序次序表中进行折半查找,最大的比较次数是 log 2 n 1；技术广泛应用于查找过程,选择 Hash函数的标准是 和；处理冲突的技术有优有劣,其共同标准是；32. 在下述排序算法中,所需帮助储备

20、空间最多的是 B ,所需帮助储备空间最小的是 C ,平均速度最快的是 A ；A.快速排序 B. 归并排序 C. 堆排序33. 在文件局部有序或文件长度较小的情形下,正确内部排序的方法是 A ；A. 直接插入排序 B. 冒泡排序 C. 简洁选择排序34. 快速排序在最坏情形下时间复杂度是 On 2 ,比 A 的性能差；A. 堆排序 B. 冒泡排序 C. 简洁选择排序35. 如需在 Onlogn 的时间内完成对数组的排序,且要求排序是稳固的,就可选择的排序方法是 C ；A. 快速排序 B. 堆排序C. 归并排序 D. 希尔排序36. 假如只想得到 1000 个元素组成的序列中第 5 个最小元素之前

21、的部分排序的序列,用 B 方法最快；A. 冒泡排序 B. 快速排序C. 希尔排序 D. 堆排序 E. 简洁选择排序37. 以下结点序列是堆的为 A ；A. 100,90,80,60,85,75,20,25,10,70,65,50B. 100,70,50,20,90,75,60,25,10,85,65,8038. 如要尽可能快地完成对实数数组的排序,且要求排序是稳固的,就应选 C ；A. 快速排序B. 堆排序C. 归并排序D. 希尔排序39. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为 A 排序法；A. 插入排序 B. 交换排

22、序C. 选择排序 D. 归并排序40. 直接插入排序在最好情形下的时间复杂度为 B ；A. Ologn B. OnC. Onlogn D. On 241. 下面函数是将任意序列调整为最大堆的算法,请将空白部分填上：将任意序列调整为最大堆通过不断调用adjust函数,即fori=n/2;i0;i- adjustlist, i, n;其中 list为待调整序列所在数组（从下标1 开头）,n 为序列元素的个数；void adjustint list, int root, int n/* 将以 root为下标的对应元素作为待调整堆的根,待调整元素放在list数组中, 最大元素下标为 n*/int ch

23、ild,rootkey; rootkey = 1 ; child = 2*root; whilechild n ifchildn & listchild listchild break; else list 3 =listchild; 4 ; list 5 =rootkey; 参考答案：1 listroot 2 child+; 3 child/2 4 child *= 2; 5 child/2 41. 表是一种数据结构,链表是一种 1 ；队列和栈都是线性表,栈的操作特性 是 2 ,队列的操作特性是 3 ；今有一空栈 S,对以下待进栈的数 据元素序列 a,b,c,d,e,f 依次进栈、进栈、出栈

24、、进栈、进栈、出栈的操作,就此操作完成 后,栈 S 的栈顶元素为 4 ,栈底元素为 5 ；供选答案：1: A. 非次序储备线性表B. 非次序储备非线性表2: C. 次序储备线性表D. 次序储备非线性表A. 随机进出B. 先进后出3: C. 先进先出D. 出优于进A. 随机进出B. 先进后出4: C. 后进后出D. 进优于出A. f B. c5: C. a D. bA. b B. cC. a D. d答案： ABCBC42. 操作系统主要是对运算机系统全部 1 进行治理,以便利用户、提高运算机使用效率的一种系统软件；它的主要功能有： 处理机治理、 储备治理、文件治理、 2 管理和设备治理等；Wi

25、ndows 和 Unix 是最常用的两类操作系统；前者是一个具有图形界面的窗口式的 3 系统软件,后者是一个基本上采纳 4 语言编制而成的的系统软件； 在 5 操作系统掌握下, 运算机能准时处理由过程掌握反馈的信息并作出响应；供选答案：1: A. 应用软件B. 系统软硬件2: C. 资源D. 设备A. 数据B. 作业3: C. 中断D. I/OA. 分时B. 多任务4: C. 多用户D. 实时A. PASCAL B. 宏5: C. 汇编D. CA. 网络B. 分时C. 批处理D. 实时答案： CBBDD43. 本程序从键盘读入整数,并按从大到小的次序输出输入整数中互不相等的那些整数；程序一边读

26、入整数, 一边构造一个从大到小次序链接的链表,直至不能从键盘读入整数,然后次序输出链表上各表元的整数值；主函数每读入一个整数,就调用函数 insert,函数 insert 将仍未显现在链表上的整数按从大到小的次序插入到链表中；为了插入便利,链表在表首有一个帮助表元；阅读以下 C代码,在 n #include #include #define NULL 0 typedef struct node int val; struct node *next; NODE; void insertNODE *list,int x NODE *u, *v, *p; u = list; v = u-next;处

27、填入相应的字句以完成上述功能；while 1 & x val /* 查找插入位置 */ u=v;v=u-next; ifv=NULL | 2 /* 判定是否要插入表元*/p = NODE *mallocsizeofNODE; p-val = x; /* 生成新表元 */ 3 = v; 4 = p; /* 插入新表元 */ main int x; NODE *head, *p;/* 第一建立只有帮助表元的空链表 */ head = NODE *mallocsizeofNODE; 5 =NULL;printf“ Enter Integers:n” ;/* 反复读入整数插入链表*/whilescan

28、f“ %d” ,&x = 1 inserthead,x; forp=head-next;p.=NULL;p=p-next /* 输出链表 */ printf“ %dt ”,p-val; printf“ n ” ; 答案：1 v .= NULL 或 v 2 x v-val 或 x .= v-val 3 p-next 4 u-next 5 head-next 44. 运算机数据处理的对象是具有不同结构的各种数据,可以拜访的最小数据信息单位是 1 ,可以引用的最小命名数据单位是 2 ；线性表按链接方式储备 线性表是最简洁的一种数据结构,有次序和链接两种储备方式；时,每个结点的包括 3 两部分；只能用

29、于顺 线性表的查找有 4 和 5 两种,但 5 序储备的情形；供选答案：1: A. 数字B. 字符2: C. 数据元素D. 数据项A. 结点B. 记录3: C. 数据元素D. 数据项A. 数据值与符号B. 数据与指针4: C. 数据与表名D. 头地址与尾地址A. 随机查找B. 次序查找5: C. 二分法查找D. 浏览A. 随机查找B. 次序查找C. 二分法查找D. 浏览答案： CDBBC 45. 本程序用于从链盘读入整数,插入到链表,或从链表删除一个整数；阅读下面的C代码,将应填入 n 处的字名写在答卷的对应栏内；#include #include typedef struct node in

30、t val; struct node * next; NODE;NODE * insNODE *list, int x /* 将 x 按从小到大的次序插入链表*/NODE *u, *v=list, *p; for; v .= NULL & x val ; v = v-next;/* 查找插入位置 */ifv .= NULL & x = v-val returnlist; /* 已有,被忽视 */p = NODE *mallocsizeofNODE;p-val=x; /* 生成新表元 */ifv = list list = p;else 1 ; 2 ; return list; NODE * d

31、elNODE * list, int x /*从链表中删除值为x 的表元 */NODE *u, *v; forv = list; v .= NULL & x valu; u=v;v=v-next;ifv .= NULL & x = v-val /* 找到值为 x 的表元 */ifv = list list = list-next;/* 释放空间 */else 3 ; 4 ; else printf“ 没有找到 .n ” ;returnlist; main int x,ans; NODE * list=NULL, *p; while1printf“ n 输入 1：将整数插入到链表；n 输入 2：

32、从链表删除一个整数；n ”;printf“ 其它整数,终止程序；nt请输入选择！”;scanf%d,&ans; if 5 return; printf“ 输入整数：”;scanf“ %d” ,&x; ifans=1 list=inslist,x; else list=dellist,x;forp=list;p.=NULL;p=p-nextprintf“ %4d” ,p-val;答案：1 u-next = p;2 p-next = v3 u-next = v-next4 freev5 ans .= 1 & ans .= 246. 从未排序的序列中,依次取出元素, 与已排序序列的元素比较后,放入已

33、排序序列中的恰当位置上,这是 1 排序；从未排序的序列中,选择出元素,放在已排序序列的某一端位置, 这是 2 排序； 逐次将待排序的序列中的相邻元素两两比较,凡是逆序就进行交换,这是 3 排序；假如整个排序过程都在内存中进行,称为 4 排序；排序算法的复杂性与排序算法的 5 有关；供选答案：1: A. 选择B. 插入2: C. 比较D. 归并A. 选择B. 插入3: C. 比较D. 归并A. 冒泡B. 交换4: C. 比较D. 散列A. 外部B. 内部5: C. 外存D. 内存A. 运算量大小与占用储备多少B. 运算量大小与处理的数据量大小C. 并行处理才能和占用储备多少D. 占用储备多少和处

34、理的数据量大小答案： BAABA47. 操作系统是对运算机资源进行的 1 系统软件,是 2 的接口；在处理机治理中,进程是一个重要的概念,它由程序块、 3 和数据块三部分组成,它有 3 种基本状态,不行能发生的状态转换是 4 ；虚拟储备器的作用是答应程序直接拜访比内存更大的地址空间,它通常使用 5 作为它的一个主要组成部分；供选答案：1: A. 输入和输出B. 键盘操作2: C. 治理和掌握D. 汇编和执行A. 软件和硬件B. 主机和外设3: C. 高级语言和机器语言D. 用户和运算机A. 进程掌握块B. 作业掌握块4: C. 文件掌握块D. 设备掌握块A. 运行态转换为就绪态B. 就绪态转换

35、为运行态C. 运行态转换为等待态D. 等待态转换为运行态5: A. 软盘B. 硬盘C. CDROM D. 寄存器答案： CDADB 48. A 是信息的载体,它能够被运算机识别、储备和加工处理；A. 数据 B. 数据元素 C. 结点 D. 数据项 C ；49. 以下程序段的时间复杂度为 fori=1;in;i+ y=y+1; forj=0;j=2*n;j+ x+; 供选答案：A. On-1 B. O2n D C. On2 D. O2n+150. 下面程序段的时间复杂度为；i=1; whilei=n i=i*2; 供选答案：A. O1 B. On B C. On2 D. Olog2n51. 下面

36、程序段的时间复杂度为；a=0;b=1; fori=2;inext & jnext;j+;ifi=jreturnp;elsereturnNULL;供选答案：A. On 2 B. O2n C. On 3 D. Ologn60. 二维数组 Amn按行序为主次序存放在内存中,每个数组元素占 1 个储备单元,就元素 aij的地址运算公式是 C ；A. LOCaij = LOCa 11+i-1*m+j-1B. LOCaij = LOCa 11+j-1*m+i-1C. LOCa ij = LOCa 11+i-1*n+j-1D. LOCa ij = LOCa 11+j-1*n+i-161. 以下哪一个不是队列

37、的基本运算 C ；A. 从队尾插入一个新元素 B. 从队列中删除第 i 个元素C. 判定一个队列是否为空 D. 读取队头元素的值62. 在一个长度为 n 的次序表中, 向第 i 个元素之前插入一个新元素,需向后移动 B 个元素；A. n-i B. n-i+1 C. n-i-1 D. i63. 从一个长度为 n 的次序表中删除第 i 个元素时,需向前移动 A 个元素；A. n-i B. n-i+1 C. n-i-1 D. i64. 在具有 n 个单元的次序储备的循环队列中,假定 front 和 rear 分别为队首指针和队尾指针,就判定队空的条件是 B ；A. front=rear+1 B. f

38、ront=rear C. front+1=rear D. front=065. 从一个具有 n 个结点的单链表中查找其值等于 x 的结点时,在查找胜利的情形下,需平均比较 D 个结点；A. n B. n/2 C. n-1/2 D. n+1/266. 一个栈的入栈序列是 a,b,c,d,e,就栈不行能的输出序列是 C ；A. edcba B. decba C. dceab D. abcde67. 栈结构通常采纳的两种储备结构是 A ；A. 次序储备结构和链表储备结构 C. 链表储备结构和数组B. 散列方式和索引方式 D. 线性储备结构和非线性储备结构68. 判定一个次序栈ST（最多元素为mo）为

39、空的条件是 B ；A. ST-top0 B. ST-top=0 C. st-topmo D. st-top=mo 69. 不带头结点的单链表 head 为空表的判定条件是 A ；A. head=NILL B. head-next=NULL C. head-next=head D. head .= NULL 70. 在一个单链表中,已知 q 所指结点是 p 所指结点的前驱结点,如在 p 和 q 之间插入 s 结 点,就应执行 C ；A. s-next = p-next; p-next=s; B. p-next = s-next; s-next=p; C. q-next = s; s-next=p

40、; D. p-next = s; s-next=q; 71. 假设双向链表结点的类型如下：typedef struct Linknode int data; /* 前驱结点指针 */ struct Linknode *lLink; struct Linknode *rLink; /* 后继结点指针 */ 下面给出的算法是要把一个 q 所指新结点, 作为非空双向链表中的 p 所指的结点前驱结点插 C ；入到该双向链表中,能正确完成要求的算法段是 Aq-rLink=p; q-lLink=p-lLink; p-lLink=q; p-lLink-rLink=q; B. p-lLink=q, q-rLi

41、nk=p; p-lLink-rLink=q; q-lLink=p-lLink; C. q-lLink=p-lLink; q-rLink=p;p-lLink-rLink=q;p-lLink=q; D. 以上均不对；72. 串是一种特别的线性表,其特别性表达在 B A. 可以次序储备 B. 数据元素是一个字符C. 可以链接储备D. 数据元素可以是多个字符73. 设有两个串p 和 q,求 q 在 p 中首次显现的位置的运算称作 B ；A. 连接B. 模式匹配C. 求子串D. 求串长74. 设串 s1=” ABCDEFG” ,s2=” PQRST” ,函数 conx,y返回 x 和 y 串的连接串,s

42、ubss,I,j返回串 s 的从序号 i 的字符开头的 j 个字符组成的子串,lens 返回串 s 的长度,就consubs1,2,lens2,subs1,lens2,2 的结果是 D ；A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF75. 常对数组进行的两种基本操作是 C ；A. 建立和删除 B. 索引和修改 C. 查找和修改 D. 索引和查找76. 稀疏矩阵一般的压缩储备方法有两种,即 ；A. 二维数组和三维数组 B. 三元组和散列C. 三元组和十字链表 D. 散列和十字链表77. 对下图所示的二叉表,按先根次序遍历得到的结点序列为 B ；A. ABCDH

43、EIFG B. ABDHIECFGC. HDIBRAFCG D. HIDBEFGAC78. 在一棵二叉树上,度为 0 的结点个数为 n0,度为 2 的结点数为 n2,就 n0= A ；A. n 2+1 B. n 2-1C. n 2 D. n 2/279. 某二叉树前序遍历结点的拜访次序是 ABCDEFG,中序遍历结点的拜访次序是 CBDAFGE,就其后序遍历结点的拜访次序是 A ；ACDBGFEA B. CDGFEABC. CDBAGFE D. CDBFAGE80. 在以下储备形式中, D 不是树的储备形式；A. 双亲表示法 B. 孩子链表表示法C. 孩子兄弟表示法 D. 次序储备表示法81.

44、 已知一棵二叉树的中序序列为 cbedahgijf,后序序列为 cedbhjigfa,就该二叉树为 B ；82. 已知一棵权集 W=2,3,4,7,8,9 的哈夫曼树,其加权路径长度 WPL为 ；A. 20 B. 40 C. 80 D. 16083. 已知一棵度为 m的树中有 n1个度为 1 的结点, n2个度为 2 的结点, , nm个度为 m的结点,问这棵树中叶子结点为 ；A. 1+niI-1 B. 1+n i I+1 C. n1+n2+ +nmD. m nm84. 如下图所示的4 棵二叉树中,不是完全二叉树；85. 设高度为 h 的二叉树上只有度为 少为 B ；0 或度为 2 的结点,就

45、此类二叉树中所包含的结点数至A. 2h B. 2h-1 C. 2h+1 D. h+186. 如下图所示的二叉树的中序遍历序列是 ；A. abcdgef B. dfebagc C. dbaefcg D. defbagc87. 已知某二叉树的后序遍历序列是 dabec,中序遍历序列是 debac,就其前序遍历序列为 D ；A. acbed B. decab C. deabc D. cedba88. 假如 T2 是由有序树 T 转换而来的二叉树, 就 T 中结点的前序就是 T2 中结点的 A ；A. 前序 B. 中序 C. 后序 D. 层次序89. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的

46、基本遍历策略可分为先序遍历、中序遍历和后序遍历；这里, 我们把由树转化得到的二叉树叫做这棵树对应的二叉树；下面结论正确选项 A ；A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B. 树的先根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上均不对90. 深度为 5 的二叉树至多有 个结点；A. 16 B. 32 C. 31 D. 1091. 在一非空二叉树的中序遍序序列中,根结点的右边 A ；A. 只有右子树的全部结点 B. 只有右子树的部分C. 只有左子树的部分结点D. 只有左子树的全部结点92. 树最适合用来表示；B. 无

47、序数据元素A. 有序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据93. 设 n,m为一棵二叉树上的两个结点,在中序遍历时,n 在 m前的条件是 C ；A. n 在 m的右方B. n是 m的祖先C. n 在 m的左方D. n 是 m的子孙94. 对一个满二叉树,m个树叶 ,n 个结点,深度为h,就 D ；A. n=h+m B. h+m=2nC. m=h-1 D. n=2h-195. 假如某二叉树的前序为stuwv ,中序为 uwtvs ,就该二叉树后序为A. uwvts B. vwutsC. wuvts D. wutsv96. 设待排序的记录为20,16,13,14,1

48、9,经过以下过程将这些记录排序；20,16,13,14,1916,20,13,14,1913,16,20,14,1913,14,16,20,1913,14,16,19,20所用的排序方法是 A ；B. 冒泡排序A. 直接插入排序C. 希尔排序D. 堆排序97. 对以下 4 个序列用快速排序的方法进行排序,以序列的第一个元素为基础进行划分,在第一趟划分过程中,元素移动次数最多的是 A 序列；A. 70,75,82,90,23,16,10,68B. 70,75,68,23,10,16,90,82C. 82,75,70,16,10,90,68,23D. 23,10,16,70,82,75,68,90

49、98. 用快速排序的方法对包含几个关键字的序列进行排序,最坏情形下,执行的时间为 D ；B. Olog2n nlog2n D. On2A. On 99. 在全部排序方法中,关键码（即关键字）比较的次数与记录的初始排列次序无关的是 D ；A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序100. 在归并排序过程中,需归并的趟数为 ；A. n B. n C. n log 2 n D. log 2 n101. 一组记录的排序代码为 46,79,56,38,40,84,就利用堆排序的方法建立的初始堆为 B ；A. 79,46,56,38,40,80 B. 84,79,56,38,40,46C. 84,79,56,46,40,38 D. 84,56,79,40,46,38102. 一组记录的排序代码为 46,79,56,38,40,84,就利用快速排序的方法,以第一个记录为基准得到的一次划分结果为 ；A. 38,40,46,56,79,84 B. 40,38,46,79,56,84C. 40,38,46,56,79,84 D. 40,38,46,84,56