下载文档原格式
中国矿业大学2011-2012学年《数据结构》试卷（A卷）（考试时间：100分钟）一. 填空（每空2分，共40分）1. 数据结构式具有相同性质的数据元素的（1）。
2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。
3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。
4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。
如果该二叉树有10层，则共有 (7) 个节点。
5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。
6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。
7. 一棵二叉树为则后序序列为（12），中序序列为（13），先序序列为__（14）____。
8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。
9.。
一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。
10. 有n个结点的无向完全图的边数分别为_______(18)_______。
11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。
12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。
石家庄学院《数据结构》期末考试试卷(A 卷)题目部分，（卷面共有135题，100分，各大题标有题量和总分）一、应用题（4小题，共8分）1．试列出下图全部可能的拓扑排序序列2．在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子序列。
若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。
3．设有上三角矩阵(aij)n*n ，将其上三角中的元素按先行后列的顺序存于数组B （1:m ）中，使得B[k]= aij 且k=f1(i)+f2(j)+c ，请推导出函数f1,f2和常数c ，要求f1和f2中不含常数项。
4．用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。
二、判断正误（20小题，共10分）1．散列表的结点中包含数据元素自身的信息，不包含任何指针。
(F)2．负载因子（装填因子）是散列表的一个重要参数，它反映敞列表的装满程度。
( T )3．一个图的广度优先搜索树是唯一的。
( F )4．外排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并的阶段。
（ T ） 5．在完成外排序过程中，每个记录的I/O 次数必定相等。
( F )6．为提高在外排序过程中，对长度为N 的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。
( F )7．在外部排序时，利用选择树方法在能容纳m 个记录的内存缓冲区中产生的初始归并段的平均长度为2m 个记录。
( T )8．堆排序是稳定的排序方法。
（ F ）9．循环队列通常用指针来实现队列的头尾相接。
（ F ） 10．有n 个数顺序(依次)进栈，出栈序列有c n 种，即：21(2)!1(!)n n C n n =⨯+。
（ T ） 11．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
( F )12．完全二叉树的某结点若无左孩子，则它必是叶结点。
（ T ） 13．深度为K 的二叉树中结点总数≤2k-1。
数据结构真题2009年下半年(总分：124.98，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00)1.按值可否分解，数据类型通常可分为两类，它们是 ( )（分数：2.00）A.静态类型和动态类型B.原子类型和表类型C.原子类型和结构类型√D.数组类型和指针类型解析：[解析] 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其值可分解为若干个成分。
2.对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陈述中不成立的是 ( )（分数：2.00）A.f(是O(g()B.g(是O(f()C.h(是O(nlog √D.h(是O(n2)解析：[解析] 当n充分大时，由题意可得：f(n)与n3是同阶的，g(n)与n3是同阶的，h(n)与n2是同阶的。
所以f(n)=O(g(n))，g(n)=O(f(n))，h(n)=O(n2)。
3.指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是( ) （分数：2.00）A.p—＞next=r; q—＞next=r—＞next; r—＞next=q; √B.p—＞next=r; r—＞next=q; q—＞next=r—＞next;C.r—＞next=q; q—＞next=r—＞next; p—＞next=r;D.r—＞next=q; p—＞next=r; q—＞next=r—＞next;解析：4.若进栈次序为a,b,e，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是 ( ) （分数：2.00）A.3B.5 √C.6D.7解析：5.假设以数组A[n]存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ( )（分数：2.00）A.rear==frontB.(front+1)%n==rearC.rear+1==frontD.(rear+1)%n==front √解析：[解析] 在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。
注意事项：1、下面关于串的叙述中，哪一个是不正确的？（ ）A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。
A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0 3、以下数据结构中，（ ）是非线性数据结构。
A ．树B ．字符串C ．队列D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。
B ．线性表采用顺序存储，便于进行插入和删除操作。
C ．线性表采用链接存储，不必占用一片连续的存储单元。
D ．线性表采用链接存储，便于插入和删除操作。
5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。
A ．(rear-front+m)%mB ．rear-front+1C ．(front-rear+m)%mD ．(rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。
A ．p->next=s; s->next=p->next;B ．s->next=p->next; p->next=s;C ．p->next=s; p->next=s->next;D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。
A ．1，2，4，3B ．2，1，3，4C ．1，4，3，2D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。
A ．a 和(b,c),d,e B ．（a ）和(b,c),d,eC ．a 和 ((b,c)，d,e)D ．(a) 和((b,c)，d,e)9、栈和队都是（ ）A ．顺序存储的线性结构B ．链式存储的非线性结构C ．限制存取点的线性结构D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。
数据结构-9(总分100, 做题时间90分钟)一、单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的1.如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用( )SSS_SINGLE_SELA 快速排序B 直接插入排序C 堆排序D 归并排序分值: 2答案:B2.设数组A[0,m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句是( )SSS_SINGLE_SELA sfront=(sfront+1)%mB sfront=(sfront+1)%(m+1)C srear=(srear+1)%mD srear=(srear+1)%(m+1)分值: 2答案:D3.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( ) SSS_SINGLE_SELA 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续不连续都可以分值: 2答案:D4.串是一种特殊的线性表，其特殊性体现在( )SSS_SINGLE_SELA 可以顺序存储B 数据元素是一个字符C 可以链接存储D 数据元素可以是多个字符分值: 2答案:B5.对广义表((a)，(b))进行下面的操作head(head((a)，(b)))后的结果是( )SSS_SINGLE_SELA aB (C ( )D 不确定分值: 2答案:A6.将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为( )SSS_SINGLE_SELA 42B 40C 21D 20分值: 2答案:D7.带头结点的单链表Head为空的判定条件是( )SSS_SINGLE_SELA Head=NULL;B Head↑.next=NULL;C Head↑.nextHead;D Head↑.next=Head↑分值: 2答案:B8.堆是一个键值序列(k1，k2，k…，k1…，k)，对i=1，2…，[n/2]，满足( )SSS_SINGLE_SEL Ak i ≤k2i≤k2i+1Bk i ＜k2i＜k2i+1Ck i ≤k2i且k≤k2i+1(2i+1≤Dk i ≤k2i或ki≤k2i+l(2i+1≤分值: 2答案:C9.链栈与顺序栈相比，有一个比较明显的优点即( )SSS_SINGLE_SELA 插入操作更加方便B 通常不会出现栈满的情况C 不会出现栈空的情况D 删除操作更加方便分值: 2答案:B10.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( )SSS_SINGLE_SELA 求关键路径的方法B 求最短路径的Dijkstra方法C 广度优先遍历方法D 深度优先遍历方法分值: 2答案:D11.如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的( )SSS_SINGLE_SELA 前序B 中序C 后序D 层次序分值: 2答案:B12.假设有一个数组，它的行号从0到8，列号从0到10，数组中每个元素所占的存储空间为3个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要( )个存储单元才能完全将此数组存放进去。
2009级《数据结构》课程试题（A卷）参考答案一、单选题：（每题 2 分，共30 分）DCDCC CABDB CCAAD二、按要求解答下列问题：（每空 5 分，共30 分）1. 算法效率和算法使用的策略、问题规模、书写语言、算法运行的软硬件环境等有关系，简要说明使用算法时间复杂度度量算法效率的思想。
不考虑计算机硬件、软件有关的因素，认为一个特定算法运行工作量的大小只依赖于问题的规模，即从算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复的次数作为算法的时间度量。
2. 证明：对任何一棵二叉树T，如果终端结点数为n0，度为2的结点数为n2，则n0=n2+1设二叉树中度为1的结点数为n1，度为2的结点数为n2，二叉树中总结点数为n，因二叉树中所有结点的度均小于或等于2，有n＝n0＋n1＋n2由于这些分支都是由度为1和2的结点射出的，所以有：B＝n1+2n2n＝n1＋2n2＋1n0+n1+n2=n1+2n2+1n0＝n2＋13. 假设有5项活动，每项活动要求的前驱活动如下：C1：无；C2：C1，C3；C3：C1；C4：C3，C5 C5：C2，C3；试根据上述关系，（1）画出相应的有向图：（2）写出拓扑排序序列；C1 ,C3, C2, C5, C44. 含12个结点的平衡二叉树的最大深度是多少（设根结点的深度为1）？画出一颗这样的树。
最大深度是55. 判别下面的每个结点序列是否表示一个堆，如果不是，请把它调整为一个堆。
（1）100 ， 90， 80，60，85，75，20，25 （2）100 ， 70， 50，20，90，75，60，25 (1) 是（2）不是 100，90，75，25，70，50，60，206. 关键字序列：22、41、53、46、30、13、01、67，h (key) = key mod 11,表长为11，用线性探测再散列处理冲突，试填写下表并计算每个关键字的冲突次数、比较次数和平均查找长度。
××科技大学成都学院二零零八至二零零九学年第一学期一．填空题（每空2分，共40分）；1.数据结构算法中，通常用时间复杂度和__空间复杂度___两种方法衡量其效率。
2.下面程序段的时间复杂度为___O(n2)______。
(n>1)for(i = 1; i <= n; i++)for(j = 1; j <= i; j++)x = x + 1;3.静态链表中指针表示的是______下一结点的地址______。
4.线型表、栈和队列都是____线型_______结构，可以在线型表的____任意___位置插入和删除元素；对于栈只能在____栈顶_____插入和删除元素；对于队列只能在____队尾___插入元素和_____队头_____删除元素。
5.在具有n个单元的循环队列中，队满时共有_____n-1____个元素。
6.在一个长度为n 的顺序表中第i 个元素（1<=i<=n）之前插入一个元素时，需向后移动__n-i+1__个元素。
7.在n个结点的单链表中要删除已知结点*p，需找到它的_____前驱________。
8.带有一个头结点的单链表head为空的条件是_________head->next==NULL__________。
9.在栈顶指针为hs的链栈中，判断栈空的条件是_________hs= =NULL__________。
10.在hq的链队列中，判定只有一个结点的条件是__hq.front->next==hq.rear________。
11.非空的循环单链表head的尾结点（由p指向），满足条件____p->next==head。
12.两个串相等的充分必要条件是______串长相等且对应字符相等_______。
13.空串是_______长度为0的串______，其长度等于___0________。
14.空格串是______由空格字符组成的串______，其长度等于_____空格的个数_________ 。
《数据结构》习题汇编09-第九章-排序-试题数据结构课程（本科）第九章试题一、单项选择题1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。
A. 直接插入排序B. 快速排序C. 归并排序D. 直接选择排序2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。
A. 起泡排序B. 快速排序C. 直接选择排序D. 堆排序3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。
这样的排序方法是（）。
A. 直接选择排序B. 直接插入排序C. 快速排序D. 起泡排序4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A. 8B. 10C. 15D. 255.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序7.下列排序算法中（）算法是不稳定的。
A. 起泡排序B. 直接插入排序C. 基数排序D. 快速排序8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是（）。
A. 3B. 4C. 5D. 69.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。
A. 5B. 6C. 7D. 810.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。
A. 起泡排序B. 希尔排序C. 快速排序D. 直接选择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。
A. 每次序列的划分应该在线性时间内完成B. 每次归并的两个子序列长度接近C. 每次归并在线性时间内完成D. 以上全是12.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。
