计算机软件技术基础试题库

(149) 假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，

(150) 在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为 2。

(151) 折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

(152) 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找。 (153) 当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1≠k2 ，但 H（k1）=H（k2），这种现象称为 冲突.

(154) 在散列函数 H(key)=key MOD p 中，p应取 素数。

(155) 设哈希表长m=14, 哈希函数H(key)=key MOD11.表中已有4个结点；addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7, 其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是 。9

(156) 希尔排序是属于 插入排序的改进方法。

(157) 给出一组关键字T＝（20,4,34,5,16,33,18,29,2,40,7），要求从下到大进行排序，试给出快速排序（选一个记录为枢纽）第一趟排序结果 。7,4,2,85,16,18,20,,29,33,40,34

(158) 大多数排序算法都有两个基本的操作： 比较和移动 。

(159) 在对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 次。6。

(160) 在插入和选择排序中，若初始数据基本正序，则选用 插入 ；若初始数据基本反序，则选用 选择 。

(161) 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。

(162) 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速排序，在最坏的情况下所需要的时间是 O(n2) (173) 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所

需要的附加空间是 O(n) 。

7． 对于n个记录的表进行2路归并排序，整个归并排序需进行 ┌log2n┐ 趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；

初始步长为4的希尔（shell）排序一趟的结果是 P A C S Q H F X R D M Y ； 二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ； 堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。

9. 在堆排序、快速排序和归并排序中，

若只从存储空间考虑，则应首先选取 方法，其次选取 快速排序方法，最后选取归并排序方法； 若只从排序结果的稳定性考虑，则应 选取 归并排序 方法； 若只从平均情况下最快考虑，则应选取 堆排序、快速排序和归并排序 方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取 堆排序 方法。 三、程序填空题

(174) 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 void reverse(pointer h) /* h为附加头结点指针；*/ { pointer p,q;

p=h->next; h->next=NULL; while((1)________) {q=p; p=p->next; q->next=h->next; h->next=(2)________; } }

(1)p!=null ∥链表未到尾就一直作

(2)q ∥将当前结点作为头结点后的第一元素结点插入

(175) 下列算法在顺序表L中依次存放着线性表中的元素，在表中查找与e相等的元素，若 L.elem[i]=e,则找到该元素，并返回i+1，若找不到，则返回“-1” ，请填空完善之。

int Locate(SeqList L，int e)

{ i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while ((i<=L.last)&&(L.elem[i]!=e) ) i++;

/*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/

if ( i<=L.last ) return(i+1); /*若找到值为e的元素，则返回其序号*/

else return(-1); /*若没找到，则返回空序号*/ }

(176) 下列算法在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1，i的合法取值范围是 1≤i≤L->last+2，请填空完善之。

void InsList(SeqList *L, int i, int e) { int k;

if((i<1) || (i>L->last+2)) printf(“插入位置i值不合法”)； if(L->last>=maxsize-1) printf(“表已满无法插入”)；

for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置*/

L->elem[k+1]=L->elem[k] ; L->elem[i-1]=e ; /*在C语言数组中，第i个元素的下标为i-1*/ L->last++ ; }

(177) 下列算法是在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1，请填空完善之。

int DelList(SeqList *L, int i, int *e) { int k;

if((i<1)||(i> L->last+1 )) printf(“删除位置不合法！”)；

*e= L->elem[i-1] ; /* 将删除的元素存放到e

所指向的变量中*/ for(k=i;i<=L->last;k++)

L->elem[k-1]= L->elem[k] ; /*将

后面的元素依次前移*/ L->last-- ; }

四、解答题

(178) 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。 (1) 写出队满的条件表达式； (2) 写出队空的条件表达式；

(3) 设m=40,rear=13,quelen=19,求队头元素的位置； (4) 写出一般情况下队头元素位置的表达式。

(179) 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。

(180) 已知一棵二叉树的前序序列为ABCDEFGH，中序序列为CBEDFAGH，请画出该二叉树。

(181) 已知一棵二叉树如图所示。请分别写出按前序、中序、后序和层次遍历是得到的顶点序列。

B D G H E F C A (182) 已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H, A,C,K,I,L,F。

(1) 写出该二叉树的后序序列； (2) 画出该二叉树；

(3) 求该二叉树的高度(假定空树的高度为－1)和度为2、度为1、及度为0的结点个数。 该二叉树的后序序列为：J,G,D,H,E,B,K,L,I,F,C,A。 该二叉树的形式如图所示：

(183) 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。对该关键字序列构造哈希表，

(184) 对于给定的一组记录的关键字{ 23,13,17,21,30,60,58,28,30,90},试分别写出冒泡排序、快速排序、堆排序、归并排序第一趟排序后的结果。

(185) 采用哈希函数Ｈ(k)=2*k mod 13并用链地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51构造哈希表。

四、算法设计题(10分) }

(186) 阅读下面的程序，说明程序的具体功能。 typedef int elementype typedef struct node { elemtype data;

strunct node *next; }linklist;

void function( linklist *head, elemtype x ) { linklist *q, *p;

J K D G B E F H I L A C