下载文档原格式
![2008~2009数据结构(A)[1]](https://uimg.taocdn.com/158573faf705cc175527095c.webp)
黑龙江大学信息科学与技术学院第二学历自学考试考试试卷数据结构与算法 课程（形式：闭卷）一、选择题（共20题，每题1分，共20分）1． 在关系R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>,<04,10>}中，数据元素05，06的前驱是〖 〗。
A) 01 B) 02 C) 03 D) 042．下面用二元组表示的数据结构，属于何种结构〖 〗。
A={K,R}K={a,b,c,d,e,f}R={r}r={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<f,e>,<f ,d>,<f,c>,<f,b>,<f,a>}A) 集合结构B) 线性结构 C) 树形结构 D) 图形结构3．在数据类型概念的定义中，数据类型是一种对数据的各方面的描述。
其中包括〖 〗。
A) 数据的来源 B) 数据的排列顺序C) 允许对数据施加的操作 D) 数据的应用4． 顺序存储的线性表L=(a 1,a 2,……,a n )，下列说法正确的是〖 〗。
A) 每个元素都有一个直接前驱和一个直接后继B) 线性表中至少要有一个元素C) 表中元素的排列顺序必须是由小到大或由大到小D) 元素的存储顺序与逻辑顺序相同5．计算一个算法的时间复杂度是指〖 〗。
A)统计一个算法执行时，实际占用的计算机时间B)计算一个算法中的循环步骤的次数C)统计算法中进行简单操作的次数D)一个算法运行时间的相对量度6．在一个长度为n的顺序表中，删除第i个元素(1≤i≤n+1)时，须向前移动的元素的个数是〖〗。
A) n-i B) n-i+1 C) n-i-1 D) i7．对顺序存储的线性表进行排序的有关叙述中，错误的是〖〗。
要求：所有的题目的解答均写在答题纸上,需写清楚题目的序号.每张答题纸都要写上姓名和学号.一、单项选择题(每小题1。
5分，共计30分）1。
数据结构是指。
A。
一种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合2. 以下算法的时间复杂度为。
void fun(int n）{ int i=1;while （i<=n)i++；}A. O（n)B. O（n)C. O(nlog2n）D。
O（log2n)3. 在一个长度为n的有序顺序表中删除元素值为x的元素时,在查找元素x时采用二分查找,此时的时间复杂度为。
A。
O（n） B. O（nlog2n）C。
O(n2） D. O(n)4. 在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为.A. O（n）B。
O（n)C. O（nlog2n）D。
O(n2)5。
若一个栈采用数组s[0。
.n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是。
A。
top++；s[top]=x； B.s[top］=x;top++；C.top-—；s［top]=x；B。
s[top］=x；top—-;6。
中缀表达式“2＊（3+4）—1”的后缀表达式是,其中＃表示一个数值的结束.A. 2#3＃4#1#*+—B. 2＃3#4＃+＊1#—C. 2#3＃4＃＊+1#—D. —+*2#3#4＃1＃7。
设环形队列中数组的下标为0~N-1，其队头、队尾指针分别为front和rear（front 指向队列中队头元素的前一个位置，rear指向队尾元素的位置）,则其元素个数为。
A。
rear-front B。
rear-front—1C. (rear—front)%N+1 D。
（rear—front+N）％N8。
若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置,队尾指针rear指向队尾元素的位置。
《数据结构》试题（A卷）（考试时间： 90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。
A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。
A.效率B.复杂度C.数据元素之间的关系D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。
A.链式存储B. 索引存储C.顺序存储D.散列存储4.下述哪一条是顺序存储结构的优点？（）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。
A.p->next=p->next->nextB.p->next=p->nextC.p=p->next;p->next=p->next->nextD.p=p->next->next6.带头结点的单链表head为空的判定条件是（）。
A.head==NULLB.head->next==NULLC.head->next==headD.head!==NULL7.非空的循环单链表head的尾结点(由p所指向)满足（）。
A.p->head==NULLB.p==NULLC.p->next==headD.p==head8.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链式存储，不必占用一片连续的存储单元。
D.线性表采用链式存储，便于插入和删除操作。
9.队列操作的原则是（）。
A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。
注意事项：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、从逻辑上可以把数据结构分为（ ）两大类。
西华大学课程考试试题卷（A 卷）试卷编号：（2008至2009学年第2学期）课程名称：数据结构考试时间：110分钟课程代码：8401801试卷总分：100分考试形式：闭卷学生自带普通计算器:否一、单项选择题（本大题共20个小题，每小题2分，共40分）1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可有多个直接后继，则该结构是（c ）A.栈 B.队列 C.树 D.图2.在数据结构中，从逻辑上可以把数据结构分成（b ）。
A．动态结构和静态结构Ｂ.线性结构和非线性结构C．紧凑结构和非紧凑结构Ｄ．内部结构和外部结构3.算法分析的两个主要方面是（a ）。
A.空间复杂性和时间复杂性 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性4.在以下的叙述中，正确的是（c ）。
A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构5.非空的循环单链表head 的尾结点（由p 所指向）满足（c ）。
A.p->next==NULL B.p==NULL C.p->next==head D.p==head 6.栈和队列的共同点是（c ）。
A.都是先进先出 B.都是先进后出C.只允许在端点处插入和删除元素 D.没有共同点7.设若入栈序列的元素顺序为X，Y，Z，判断下列哪一个出栈序列是不可能的。
（c ）。
A．XYZ B.YZX C.ZXY D.ZYX 8.设数组Data[0..m-1]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为（b ）。
A.front=front+1 B.front=(front+1)%m C.rear=rear+1 D.rear=(rear+1)%m 9.深度为5的二叉树至多有（d ）个结点。
数据结构试卷一、填空殖（每空1分共20分)1.数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情况。
2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___;若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域.3.设输入序列为1、2、3，则经过栈的作用后可以得到_____6______种不同的输出序列。
4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的___出度_____,第i列上所有元素之和等于顶点i的____入度____。
5.设哈夫曼树中共有n个结点,则该哈夫曼树中有___0_____个度数为1的结点。
6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为____e=d_____。
7.____中序______遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序）.8.设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。
9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为______1______。
10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为___i/2_________,右孩子结点的编号为____2i+1_______。
11.设一组初始记录关键字为（72，73,71，23,94,16,5），则以记录关键字72为基准的一趟快速排序结果为_____5 16 71 23 72 94 73______。
12.设有向图G中有向边的集合E=｛〈1，2〉，<2,3>，〈1，4〉，〈4,2>，〈4，3〉｝，则该图的一种拓扑序列为___1 4 2 3___。
安徽大学计算机科学与技术学院2009 ——2010学年第二学期计算机科学与技术专业2008年级数据结构课程(测验)学号姓名得分（闭卷120分钟）1．线性表不具有的特点是（B ）。
A．可随机访问任一元素B．插入删除不需要移动元素C．不必事先知道存储空间D．所需空间与线性表长度成正比2．已知L是带头结点的单链表，指针P指向的结点既不是首元结点，也不是尾元结点，在P结点后插入S结点的语句序列是BC 。
A．P->next=S->next B．S->next=P->nextC．P->next=S D．S->next=P3．设一个栈的输入序列为1，2，3，4，则所得的输出序列可能是ABC 。
A．1，2，3，4 B．4，3，2，1C．1，3，4，2 D．4，1，2，34．队列操作的原则是 A 。
A．先进先出B．后进先出C．只能进行插入D．只能进行删除5.串是 D 。
A．不少于一个字母的序列B．任意个字母的序列C．不少于一个字符的序列D．有限个字符的序列6．在主串S中查找子串t的第1次出现的位置的操作称为 BC 。
A．字符串的查找B．字符串的定位C．模式匹配D．字符串的操作7. 在数组A中,每个元素占3个字节,行下标i从1到8,列下标j从1 到10,从首地址SA开始连续存放在存储器中,该数组按列存放时,元素A[5][8]的起始地址为B 。
A．SA+141 B．SA+180C．SA+222 D．SA+2258．广义表（（a,b），c,d）的表头是 C 。
A ．aB ． （a ）C ． （a,b ）D ． （（a ））二、填空题（每空２分，共12分）1．下面程序段中语句 k+=10*i 的执行次数是 n-1 。
i =1;k=0; while (i<=n-1 ){k+=10*i ; i++;}2．在顺序表中插入一个元素，需要平均移动 n/2 元素，具体移动的元 素个数与_插入位置和表长__________________有关。
2008年安徽工业大学数据结构考研真题A卷一、单项选择题1.程序段FOR(i=n-1;i>=0;i--)FOR(j=1;j<=n;j++)IFA[j]>A[j+1]A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是______。
A.O（n）B.O(nlogn)C.O(n✁)D.O(n)2.用链表表示线性表的优点是______。
A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同3.带头结点的单链表head为空的判定条件是_______。
A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL4.在循环双链表的p所指结点之后插入s所指结点的操作是____。
A.p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;5.栈应用在______。
A.递归调用B.子程序调用C.表达式求值D.A，Ｂ，Ｃ都对6.设abcdef(a先进栈)顺序进栈，若在进栈操作时，允许出栈操作,则下面得不到的序列为______。
A．fedcbaB.bcafedC.dcefbaD.cabdef注：序列xyz表示x先出栈；z最后出栈。
7.若一个栈的输入序列为1,2,3,4,5则输出序列有______种可能。
数据结构考试试题题库一、选择题1. 在数据结构中，栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的任意位置插入和删除元素B. 只能在表的一端进行插入和删除操作C. 只能在表的两端进行插入和删除操作D. 只能在表的中间进行插入和删除操作答案：B2. 假设有一个单链表，头结点的指针域为head，链表中每个结点包含一个数据域data和指向下一个结点的指针域next。
若要删除指针p所指向的结点，以下哪个操作是正确的？A. p = p->nextB. p->next = p->next->nextC. p = p->next->nextD. p = NULL答案：B3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根节点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根节点，最后遍历右子树C. 先遍历右子树，然后访问根节点，最后遍历左子树D. 同时遍历左子树和右子树答案：A4. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再哈希法D. 排序法答案：D5. 快速排序算法的时间复杂度在最好、最坏和平均情况下分别是：A. O(n log n), O(n^2), O(n)B. O(n), O(n log n), O(n^2)C. O(n log n), O(n), O(n log n)D. O(n^2), O(n log n), O(n)答案：A二、简答题1. 请简述什么是图，并说明图的两种基本表示方法。
答案：图是一种数据结构，由顶点（或称为节点）和边组成。
图可以表示为有向图或无向图。
图的两种基本表示方法为邻接矩阵和邻接表。
邻接矩阵是一个二维数组，其元素表示顶点之间的连接关系；邻接表则使用链表存储每个顶点的邻接点。
2. 什么是二叉搜索树（BST）？请简述其特点。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。
题一二三四五总分总评分人复查人分值40203010100得分湛江师范学院2008年－2009学年度第1学期期末考试试题A卷(考试时间:120分钟)考试科目： 数据结构请将所有答案填写在答题卡上，交卷时请将所有试卷上交一、单选题(每小题2分，共40分)1．下列算法的时间复杂度是（ B ）。
for ( i=0; i<n; i++) c[i][j]=i+j;A O(1)B O(n)C O(log 2n)D O(n 2)2．每一个存储结点不仅含有一个数据元素，还包含一个指针，该存储方式是（ B ）存储方式。
A 顺序B 链式C 索引D 散列3．指针p 指向以L 为头指针的循环链表的首元素的条件是（ A ）。
A p==L B p->next==L C L->next==p D p->next==NULL 4．4个元素进S 栈的顺序是A 、B 、C 、D ，进行两次Pop(S,x)操作后，栈顶元素的值是（ B ）。
A AB BC CD D5．经过下列栈的运算后GetTop(S)的值是（ A ）。
InitStack(s); Push(s,a); Push(s,b); Pop(s); A a B b C 1 D 2（ ）（ ）6．栈的特点是（ B ）。
A 先进先出B 后进先出C 后进后出D 不进不出7．经过下列运算后GetHead(Q)的值是（A ）InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b);A aB bC 1D 28．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（C ）。
A 1000B 1010C 1008D 10209．二叉树第i层上最多有（C ）个结点。
A 2iB 2i-1C 2i-1D i210．满二叉树（A ）二叉树。
A 一定是完全B 不一定是完全C 不是D 不是完全11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while ( p->rchild!=null ) p=p->rchild，则（A ）。
××科技大学成都学院二零零八至二零零九学年第一学期一．填空题（每空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.空格串是______由空格字符组成的串______，其长度等于_____空格的个数_________ 。
2008级数据结构试卷A及答案(A) Improve the basic operations. (B) Minimize the number of disk accesses.(C) Eliminate the recursive calls. (D) Reduce main memory use.(7) The max-heap constructed by a sequence of key (54, 32, 45, 63, 76, 84) is( D )?(A) 84, 63, 54, 76, 32, 45 (B) 84, 76, 45, 63, 54, 32(C) 84, 63, 76, 32, 45, 54 (D) 84, 76, 54, 63, 32, 45(8) If there is 1MB working memory, 8KB blocks, yield 128 blocks for working memory. By the multi-way merge in external sorting, the average run size and the sorted size in one pass of multi-way merge on average are separately ( C )?(A) 1MB, 128 MB (B) 2MB, 512MB(C) 2MB, 256 MB (D) 1MB, 256MB(9) Tree indexing methods are meant to overcome what deficiency in hashing?( D )(A) Inability to handle range queries. (B) Inability to maximum queries(C) Inability to handle queries in key order (D) All of above.(10) Assume that we have eight records, with key values A to H, and that they are initially placed in alphabetical order. Now, consider the result of applying the following access pattern: F D F G E G F A D F G E, if the list is organized by the move-to-front heuristic, then the final list will be ( B ).(A)E G F D A C H B (B) E G F D A B C H(C) F D G A E C B H (D) F D G E A B C H2. Fill the blank with correct C++ codes: (15 scores)(1)Given an array storing integers ordered by value, modify the binary searchroutines to return the position of the first integer with the greatest value less than K when K itself does not appear in the array. Return ERROR if the least value in the array is greater than K: (12 scores)// Return position of greatest element <= Kint newbinary(int array[], int n, int K) {int l = -1;int r = n; // l and r beyond array boundswhile (l+1 != r) { // Stop when l and r meet___ int i=（l+r）/2_____; // Look at middle of subarrayif (K < array[i]) __ r=i ___; // In left halfif (K == array[i]) __ return i ___; // Found itif (K > array[i]) ___ l=i ___ // In right half}// K is not in array or the greatest value is less than Kif K> array[0] （or l !=-1）then return l ; // the first integer with the greatest value less than// K when K itself does not appear in the array else return ERROR; // the least value in the array is greater than K}(2) A full 6-ary tree with 100 internal vertices has ___601___vertices. ( 3 scores)3. A certain binary tree has the preorder enumeration as ABECDFGHIJ and the inorder enumeration as EBCDAFHIGJ. Try to draw the binary tree and give the postorder enumeration. (The process of your solution is required) (8 scores)Postorder enumeration : EDCBIHJGFA4. Determine Θ for the following code fragments in the average case. Assume that all variables are of type int.(6 scores)(1) sum=0;for (i=0; i<3; i++)for (j=0; jsum++; solution : Θ___(n)_______(2) sum = 0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)sum++; solution : Θ__(n 2)________(3) sum=0;if (EVEN(n))for (i=0; isum++;elsesum=sum+n; solution : Θ___(n)_____5. Trace by hand the execution of Quicksort algorithm on the array:int a[] = {265 301 751 129 937 863 742 694 76 438} The pivot is 265 in the first pass, the second is 76 and 751, the third is 438 and 863, the four is 694, and so on till the algorithm is finished. (9 scores)initial: 265 301 751 129 937 863 742 694 76 438pass 1: [76 129] 265 [751 937 863 742 694 301 438]pass 2: 76 [129] 265 [438 301 694 742] 751 [863 937]pass 3: 76 129 265 [301] 438 [694 742] 751 863 [937]pass 4: 76 129 265 301 438 694 [742] 751 863 937pass 5: 76 129 265 301 438 694 742 751 863 937final sorted array:76 129 265 301 438 694 742 751 863 9376. Build the Huffman coding tree and determine the codes for the following set of letters and weights:A B C D E F G H5 25 36 10 11 36 4Draw the Huffman coding tree and give the Huffman code for each letters. What is the expected length in bits of a message containing n characters for this frequency distribution? (The process of your solution is required) (9 scores)Total length: 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257Expected length: 257/100=2.577. Assume a disk drive is configured as follows. The total storage is approximately 675M divided among 15 surfaces. Each surface has 612 tracks; there are 144 sectors/track, 512 byte/sector, and 16 sectors/cluster. The interleaving factor is five. The disk turns at 7200rmp (8.33 ms/r). The track-to-track seek time is 20 ms, and the average seek time is 80 ms. Now how long does it take to read all of the data in a 320 KB file on the disk? Assume that the file ’s clusters are spread randomly across the disk. A seek must be performed each time the I/O reader moves to a new track. Show your calculations. (The process of your solution is required) (8 scores)Answer ：The first question is how many clusters the file requires?DA cluster holds 16*0.5K = 8K. Thus, the file requires 320/8=40 clusters.The time to read a cluster is seek time to thecluster+ latency time + (interleaf factor ×rotation time).Average seek time is defined to be 80 ms. Latency time is 0.5 *8.33 ms(60/7200≈8.33ms),and cluster rotation time is 5 * (16/144)*8.33.Seek time for the total file read time is40* (80 + 0.5 *8.33+ 5 * (16/144)*8.33 ) ≈3551.85 ms Or 3551.51 when (60/7200≈8.3ms)8. Using closed hashing, with double hashing to resolve collisions, insert the following keys into a hash table of eleven slots (the slots are numbered 0 through 10). The hash functions to be used are H1 and H2, defined below. You should show the hash table after all eight keys have been inserted. Be sure to indicate how you are using H1 and H2 to do the hashing. ( The process of your solution is required)H1(k) = 3k mod 11 H2(k) = 7k mod 10+1Keys: 22, 41, 53, 46, 30, 13, 1, 67. (8 scores)Answer:H1(22)=0, H1(41)=2, H1(53)=5, H1(46)=6, no conflictWhen H1(30)=2, H2(30)=1 （2+1*1）%11=3，so 30 enters the 3rd slot;H1(13)=6, H2(13)=2 (6+1*2)%11=8, so 13 enters the 8th slot;H1(1)=3, H2(1)=8 (3+5*8)%11= 10 so 1 enters 10 (pass by 0, 8, 5, 2 );H1(67)=3, H2(67)=10 (3+2*10)%11= 1 so 67 enters 1(pass by 2)9. You are given a series of records whose keys are integers. The records arrive in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R. Show the 2-3 tree that results from inserting these records. （the process of your solution is required）(7 scores)MSBD P UA C GI N R T W10.1) Use Dijkstra’s Algorithm to find the shortest paths from C to all other vertices.(4 scores)2) Use Kruskal’s algorithm to find the minimum-cost spanning tree. (3 scores)3) Show the DFS tree for the following graph, starting at Vertex A. (3 scores)1)C to A: 4 (C,A); CF: 5(C,F); CD: 6(C,A,D); CB: 12(C,A,D,B); CG:11 (C,F,G); CE: 13(C,A,D,B,E)2)OR3)A---->B---->D--->F---->C GE。
数据结构考试题库含答案数据结构习题集含答案目录选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的（A ）A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（D ）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.*数据结构是指（A ）。
A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。
A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（A ）。
A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性8.计算机内部处理的基本单元是（B ）A、数据B、数据元素C、数据项D、数据库9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（B ）。
A、低B、高C、相同D、不好说10.算法的时间复杂度取决于（ C ）A 、问题的规模B、待处理数据的初始状态C、问题的规模和待处理数据的初始状态D、不好说11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。
A、正确B、错误C、前半句对，后半句错D、前半句错，后半句对12.在数据结构中，从逻辑上可以把数据结构分成（ C ）A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ）存储结构。
广东商学院试题纸
2008-2009 学年第二学期考试时间共120 分钟
课程名称数据结构（A卷）课程代码110104 课程班号共_3_页------------------------------------------------------------------------------------------------------------------------
一、单选题（每小题1分，共20分）
（注意：请将本题答案写在答题纸第1页的单项选择题表格中）
1、数据结构是指【】。
A．数据类型B．数据定义C．数据的存储结构D．数据的组织形式
2、从有n个结点的单链表中查找值为x的结点时，在查找成功的情况下，需平均比较【】个结点。
A．n B．n/2 C．(n-1)/2 D．(n+1)/2
3、一个顺序队列第5个元素的存储地址是200，第10个元素的存储地址是225，则第20个元素的存储地址是【】。
A．220 B．230 C．270 D．275
4、判断一个顺序栈(最多有m个元素)为空的条件是【】。
A．S.base==0 B．S.top==-1 C．S.top==S.base D．S.top-S.base>=m
5、判断一个顺序循环队列Q（最多m个元素）为满的条件是【】。
A．Q.front==Q.rear B．Q.front!=Q.rear
C．Q.front==(Q.rear+1)%m D．Q.rear==(Q.front+1)%m
6、有100个叶结点的哈夫曼树共有【】个结点。
A．101 B．199C．200 D．201
7、设高度为h的二叉树只有度为0和度为2的结点，则此类二叉树的结点数至少为【】个。
A．2h B．2h-1 C．2h+1 D．h+1
8、5层的二叉树至多有【】个结点。
A．10 B．16 C．31 D．32
9、深度为h的完全二叉树中，编号最小的叶结点的编号是【】。
A．2h-1B．2h-1 C．2h-1+1 D．2h-2+1
10、森林的中序遍历序列与对应的二叉树的【】遍历序列一致。
A．先序B．中序C．后序D．不可能
11、要连通有n个顶点的无向图至少需要【】条边。
A．n B．n/2 C．n-1D．n+1
12、在一个无向图中，所有顶点的度数之和等于所有边数之和的【】倍。
A．1/2 B．1 C．2 D．4
13、设有100个数据元素，采用折半查找时最大的关键字比较次数是【】。
A．5 B．6 C．7 D．8
14、对关键字序列{50，70，40，85，75，20，35，45，65，30}建立二叉排序树，查找元素35需进行【】次关键字的比较。
A．2 B．3 C．4D．5
15、m阶B-树中所有内部结点的关键字个数必须大于或等于【】。
（注：「」代表向上取整）A．「m/2」B．「m/2」-1 C．「m/2」+1 D．m
16、就平均性能而言，目前最好的排序方法是【】。
A．起泡排序B．希尔排序C．选择排序D．快速排序
17、在待排序列基本有序的前提下，效率最高的排序方法是【】。
A．插入排序B．归并排序C．选择排序D．快速排序
18、下述几种排序方法中，要求内存量最大的是【】。
A．插入排序B．选择排序C．快速排序D．归并排序19、堆是一种基于【】原则的排序方法。
A．插入B．选择C．交换D．归并
20、对n个不同的记录进行起泡排序，在正序的情况下关键字比较的次数为【】。
A．n B．n-1 C．n+1 D．n（n-1）/2
二、填空题（每小题1分，共10分）
1、在队列中存取数据应遵循的原则。
2、由一棵二叉树的后序序列和可唯一确定这棵二叉树。
3、具有n个分支的二叉树，共有个结点。
4、图的存储方式中，邻接多重表用于图的存储。
5、运行图的深度优先遍历算法需要结构的支持。
6、对AOV网运行算法，目的是判断工程能否完工。
7、求最小生成树的算法，适用于稠密图。
8、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。
9、对二叉排序树进行平衡化处理的目的，是使最小。
10、基数排序的两个子过程是和收集。
三、简答题（每小题分，共分）
四、综合题（每小题分，共分）
五、算法设计（共8 分）
现有一个带头结点的单链表L，要求：
（1）写出单链表存储结构的定义；（3分）
（注：结点LNode，单链表LinkList）
（2）编写一个返回L中值为x的结点的位序的算法Locate_LinkList。
（5分）（注：算法可用类C或其他语言描述，适当加上说明，以增加可读性）。
