(109) 一个算法的效率可分为 时间 效率和 空间 效率。
(110) 对于给定的n个元素,可以构造出的逻辑结构有 集合，线性表，树，图四种。 (111) 顺序映象的特点是借助元素在存储器中的 相对位置来表示数据元素之间的逻辑关系。非顺序映象的特点是借助是指示元素存储地址的 指针表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定 逻辑结构，而算法的实现依赖于采用的 存储结构。
(112) 数据类型是一组___________性质相同的值集合以及定义在这个值集合上的一组操作的总称。
(113) 数据对象是___________性质相同的数据元素的集合，是数据的一个子集。
(114) 如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为 型运算。引用
(115) 算法的 健壮特性是指做为一个好的算法，当输入的数据非法时，也能适当地做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。
(116) 算法分析不是针对实际执行时间的精确的算出算法执行具体时间的分析，而是针对算法中语句的 执行次数做出估计，从中得到算法执行时间的信息。
(117) T(n)=O(f(n))，它表示随问题规模n的增大算法的执行时间的增长率和f(n)的增长率 相同，称作算法的渐进时间复杂度，简称时间复杂度。
(118) 若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为 原地工作，辅助空间为O(1)。
(119) 在带有头结点的单链表中L中，第一个元素结点的指针是 。L->next (120) 在一个带头节点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= 。p->next->next
(121) 设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x
的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句: py->next=px->next; px->next=py。
(122) 对于栈操作数据的原则是 。后进先出
(123) 设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为 。(rear-front+m)%m
(124) 若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1= =n,则pi为 。n-i+1
(125) 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
(126) 通常程序在调用另一个程序时，都需要使用一个 栈来保存被调用程序内分配的局部变量。形式参数的存储空间以及返回地址。
(127) 栈下溢是指在___栈空_____时进行出栈操作。
(128) 用P表示入栈操作，D表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的P和D的操作串为_______ 。PDPPDPDD
(129) 在具有n个单元的循环队列中，队满共有 n-1个元素。
(130) 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
(131) 循环队列的引入，目的是为了克服_______假溢出。
(132) 所谓稀疏矩阵指的是_______非零元很少(t< (133) 在稀疏矩阵表示所对应的三元组线性表中，每个三元组元素按 行为主序， 列号为辅序的次序排列。 (134) 二位数组Am×n按行优先顺序存储在内存中，元素a00地址为loc(a00),每个元素在内存中占d个字节，元素aij的地址计算公式为loc(aij)= loc(a00)＋(i*n+j)*d 。 (135) 树内个结点的度 最大值称为树的度。 (136) 一个二叉树第5层节点最多有 16个。 (137) 已知完全二叉树T的第5层只有7个结点，则该树共有____11____个叶子结点。 (138) 在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______N2+1。 (139) 假设用于通信的电文由8个字母组成，其频率分别为7,19,2,6,32,3,27,10。设计哈夫曼编码，其中字母的编码长度最大是 5位。 (140) 一棵具有257个结点的完全二叉树，它的深度为 。 9 (141) 散列法存储的基本思想是由 关键字的值决定数据的存储地址。 (142) 大多数排序算法都有两个基本的操作： 。比较和移动 (143) 由于查找算法的基本运算是关键字之间的比较操作，所以可用 平均查找长度来衡量查找算法的性能。 (144) 查找有静态查找和动态查找，当查找不成功时动态查找会 将查找关键字插入在表中。 (145) 顺序查找法中设置监视哨，可以起到 防止越界的作用。 (146) 假设列表长度为n，那么查找第i个数据元素时需进行 n-i+1次比较。 (147) 假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为： ASL=(n+1)/2。 (148) 折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是 按关键字大小有序排列的顺序表。 (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 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库计算机软件技术基础试题库(3)在线全文阅读。
相关推荐：