2000年北京工业大学数据结构试题

第九章集合一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

【北京航空航天大学 2000 一、8 （2分）】A． (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/23．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。

在此假定N为线性表中结点数，且每次查找都是成功的。

【长沙铁道学院 1997 四、3 (4分)】A.N+1B.2log2NC.logND.N/2E.Nlog2NF.N24. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储5. 对线性表进行二分查找时，要求线性表必须（）【燕山大学 2001 一、5 （2分）】A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序6．适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 （2分）】A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序 D．顺序方式存储，元素有序7. 用二分（对半）查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 （2分）】A．必然快 B. 必然慢 C. 相等 D. 不能确定8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减【南京理工大学 1997 一、7 （2分）】9. 具有12个关键字的有序表，折半查找的平均查找长度（）【中山大学 1998 二、10 （2分）】A. 3.1B. 4C. 2.5D. 510. 折半查找的时间复杂性为（）【中山大学 1999 一、15】A. O（n2）B. O（n）C. O（nlog n）D. O（log n）11．当采用分快查找时，数据的组织方式为 ( ) 【南京理工大学 1996 一、7 （2分）】A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

北京工业大学2000年硕士研究生入学考试试题考试科目：数据结构注意：试题中编程一律要求采用类PASCAL语言。

一、选择（单选、多选）与填空题1．（10分每问2分）下列内部排序算法中：A．快速排序 B. 直接插入排序 C. 二路归并排序 D. 简单选择排序E. 起泡排序F. 堆排序①其比较次数与序列初态无关的是（）② 不稳定的排序是（ ）③ 在初始序列已基本有序（除去n个元素中的某个k元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（ ）④ 排序的平均时间复杂度为O(n•logn)的算法是（ ）为O(n•n)的是（ ）2.（3分）在用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k （ ）A 有关B 无关3．（4分）在m阶B-树的某结点中插入一个关键字而引起的结点分裂，则其中原有（ ）个关键字；从m阶Ｂ－树的某结点中删除一个关键字而引起的结点合并，则其中原有（ ）个关键字二、简答题１．（９分）对角矩阵Ａ（n*n）按行主序压缩存储于一维数组Ｂ中，其中Ａ[i,j]＝Ｂ[k]，请求出用i,j表示的k以及用k表示的i和j.２．（６分）画出广义表的存储结构示意图（两种结构中的任意一种皆可，要求共享相同子表）。

Ａ＝（c,(a,b),(d,(c,(a,b))),((c,(a,b)),((())))）３．（５分）求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。

要求写出简要步骤。

三、（８分）采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［０..１２］中对关键字序列２２，４１，５３，４６，３０，１３，６７，５１（１）构造哈希表（画示意图，并求：（２）装填因子；等概率下（３）成功的和（４）不成功的平均查找长度。

四、（１５分）循环链表a和b的结点值为字母，其中a表非递减有序，下面的程序欲构造一个递增有序的循环连表c，其中结点的值为同时在a，b两链表中出现的字母，且c中字母不重复，请补上程序中空缺的部分，并估计算法的时间复杂度。

7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000 一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。

试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。

表左的s指向起始表元。

供选择的答案：A.连续B.单向链接C.双向链接D.不连接E.循环链接F.树状G.网状H.随机I.顺序J.顺序循环【上海海运学院 1995 二、1（5分）】12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（）【南京理工大学 2000 一、3（1.5分）】A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

计算机专业基础综合数据结构（排序）历年真题试卷汇编3(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：36.00)1.下面给出的四种排序法中，( )排序法是不稳定性排序法。

【北京航空航天大学1999一、10(2分)】A.插入B.冒泡C.二路归并D.堆√2.下列排序算法中，其中( )是稳定的。

【福州大学1998一、3(2分)】A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序√3.稳定的排序方法是( )。

【北方交通大学2000二、3(2分)】A.直接插入排序和快速排序B.折半插入排序和起泡排序√C.简单选择排序和四路归并排序D.树形选择排序和Shell排序4.下列排序方法中，哪一个是稳定的排序方法?( )。

【北方交通大学2001一、8(2分)】A.直接选择排序B.二分法插入排序√C.希尔排序D.快速排序5.下列排序算法中，( )是稳定排序。

【北京理工大学2007一、10(1分)】A.希尔排序B.快速排序C.堆排序D.直接插入排序√6.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

( )就是不稳定的排序方法。

【清华大学1998一、3(2分)】A.起泡排序B.归并排序C.Shell排序√D.直接插入排序E.简单选择排序√7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。

【中科院计算所2000一、5(2分)】A.直接插入√B.直接选择C.堆D.快速E.基数8.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。

【中国科技大学1998二、4(2分)】【中科院计算所1998二、4(2分)】A.快速排序B.堆排序C.归并排序√D.直接插入排序9.下面的排序算法中，不稳定的是( )。

【北京工业大学1999一、2(2分)】A.起泡排序B.折半插入排序C.简单选择排序√D.希尔排序√E.基数排序下列内部排序算法中：【北京工业大学2000一、1(10分每问2分)】A．快速排序B．直接插入排序C．二路归并排序D．简单选择排序E．起泡排序（分数：8.00）(1).其比较次数与序列初态无关的算法是( )A.B.C. √D. √E.(2).不稳定的排序算法是( )A. √B.C.D. √E.(3).在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k<A.B. √C.D.E.(4).排序的平均时间复杂度为O(n*10gn)的算法是( )，为O(n*n)的算法是( )A. √B. √C. √D. √E. √10.排序趟数与序列的原始状态有关的排序方法是( )排序法。

11．在下面的程序段中，对x 的赋值语句的频度为（c ）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（d ）A． O（n） B. O(nlogn) C. O(n3) D. O(n2)3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( f)5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。

( t)8．数据的物理结构是指数据在计算机内的实际存储形式。

(t )13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (f ) 3．数据的逻辑结构是指:数据的组织形式，即数据元素之间逻辑关系的总体。

而逻辑关系是指数据元素之间的关联方式或称“邻接关系”4．一个数据结构在计算机中称为存储结构:表示（又称映像）9．已知如下程序段FOR i:= n DOWNTO 1 DO {语句1}BEGINx:=x+1；{语句2}FOR j:=n DOWNTO i DO {语句3}y:=y+1; {语句4}END；语句 1 执行的频度为（1）；语句2 执行的频度为（2）；语句3 执行的频度为（3）；语句4 执行的频度为（4）。

9．（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2。

10．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n 的函数）FOR i：＝１ TO n DOFOR j：＝１ TO i DOFOR k：＝1 TO j DOｘ：＝ｘ＋delta；10．1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6 O(n3)3. 数据类型和抽象数据类型是如何定义的。

北京工业大学计算机学院《数据结构与算法》考试题考试形式：可带一张A4纸考试时间：**** 年**月**日学号____________________ 姓名_____________________一、填空题（10分）1．数据结构在计算机中的表示被称为_______________________________________ 。

2．通常，在队列采用顺序存储结构表示时都将首尾相接构成循环队列，其主要原因是______________________________________________________ 。

3．如果稀疏矩阵A为m行n列，且包含t个非零元素，那么，当采用三元组表示法存储这个矩阵时，快速转置算法的时间复杂度为____________________________________。

4．将二叉排序树调整为平衡二叉树的目的是__________________________________。

5．快速排序、堆排序和归并排序的时间复杂度都是O(nlogn)，但其中只有一种方法具有稳定性，它是___________________________________。

下列每个题中有四个选项，其中只有一个是正确的，请根据题目的陈述进行选择，并在选择的标号前画“ ”。

1．算法的时间复杂度是指__________________________________________。

A．算法执行的绝对时间Ｂ．随着问题规模n的增大，算法执行时间的增长趋势Ｃ．算法中执行语句的条数Ｄ．获得算法执行时间的复杂程度2．对于长度为13的有序表，如果按照二分查找法进行查找，在表内各元素等概率的情况下，查找成功的平均查找长度ASL为__________________________________。

A．6/13 Ｂ．40/13Ｃ．41/13 Ｄ．91/133．无向图的最小生成树是指____________________________________________。

计算机2000-1、2、3、4、5数据结构考试试题参考答案一、 单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干的括号内。

每小题2分，共20分）1．B 2．B 3．B 4．A 5．A 6．B 7．A 8．C 9．C 10. D 二、判断题（判断下列各题是否正确，正确在括号内打“√”，错的打“×”。

每小题1分，共10分）1．× 2．× 3．√ 4．× 5．√ 6．× 7．× 8．× 9．× 10．× 三、填空题（每题2分，共20分） 1．P->next->next 2．2m-13．mid-1 R[mid].KEY==K 或 l>h 4．R->next->next 5．36．q->next->prior=S7．第i 列非零元素之和（第i 列非零元素个数，∑=nk aki 1）第i 行非零元素之和（第i 行非零元素个数，∑=nk aik 1）8．Ls==NULL ls=ls->link 9．Lq->front==lq->rear 10．a b e f c d g四、应用题（共36分） 1．（6分） （1）(4分)解：由题义知 m=13a)因为 h(35)=35 % 13 =9 但位置9不是35，所以又双重散列得 h1(35)=35 % 11 +1=3所以 h1=(9+1*3) % 13=12 但位置12 不是 35，所以 又双重散列得h2=(9+2*3) % 13 =2 可知，位置2 是 35 ，所以 查找35共比较了3次。

b)因为 h(20)=20 % 13 = 7 但位置7不是20，所以又双重散列得 h1(20)=20 % 11 +1=10h1=(7+1*10) % 13 =4 可知，位置4 是 20 ，所以 查找20共比较了2次。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编3(总分66, 做题时间90分钟)6. 综合题1.数组A[1．．8，一2．．6，0．．6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4，2，3]的存储首地址。

【厦门大学1998五、1(5分)】SSS_TEXT_QUSTI2.数组A中，每个元素A[i，f]的长度均为32个二进位，行下标从一1到9，列下标从1到11，从首地址S开始连续存放在主存储器中，主存储器字长为16位。

求：(1)存放该数组所需多少单元?(2)存放数组第4列所有元素至少需多少单元?(3)数组按行存放时，元素A[7，4]的起始地址是多少?(4)数组按列存放时，元素A[4，7]的起始地址是多少?【大连海事大学1996四、1(6分)】SSS_TEXT_QUSTI3.假设按低下标优先存储整型数组A(一3：8，3：5，一4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占4字节，问A(0，4，一2，5)的存储地址是什么? 【清华大学1996三】SSS_TEXT_QUSTI4.设有五对角矩阵A=(aij )20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15，16]的存储位置。

【东北大学1999一、2(4分)】SSS_TEXT_QUSTI5.数组A[0．8，1．．10】的元素是6个字符组成的串，则存放A至少需要多少字节?A的第8列和第5行共占多少字节?若A按行优先方式存储，元素A[8，5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致?【厦门大学2000五、3(14％／3分)】SSS_TEXT_QUSTI6.设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[t+1)，1．．3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义?【北京航空航天大学1998一、5(4分)】SSS_TEXT_QUSTI设有三对角矩阵(aij )n×n将其三条对角线上的元素逐行地存于数组B(1：3n一2)中，使得s[k]=ai，j，求：SSS_TEXT_QUSTI7.用i，j表示k的下标变换公式；SSS_TEXT_QUSTI8.若n=10 3，每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元?【西安电子科技大学1996二、4(5分)】9.已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构(二维数组和三元组表)完成求运算的优缺点。