学年二学期数据结构期末考试试卷(A卷).doc

石家庄学院2011-2012学年第二学期数据结构期末考试试卷石家庄学院数据结构期末考试试卷(A卷)题 目一二三四五六七总 分核分人复查人得分题目部分，（卷面共有135题，100分，各大题标有题量和总分）评卷人得分一、应用题（4小题，共8分）1试列出下图全部可能的拓扑排序序列2在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。3设有上三角矩阵(aij)n*n，将其上三角中的元素按先行后列的顺序存于数组B（1:m）中，使得Bk= 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个数顺序(依次)进栈，出栈序列有种，即：。 （ T ）11顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( F ) 12完全二叉树的某结点若无左孩子，则它必是叶结点。（ T ）13深度为K的二叉树中结点总数2k-1。（ T ）14对于有N个结点的二叉树，其高度为log2n。（ F ）15一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ F ）16完全二叉树中，若一个结点没有左孩子，则它必是树叶。（ T ）17一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ T ）18由一棵二叉树的前序序列和后序序列可以唯一确定它。（ F ）19哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 ( F )20二维数组是其数组元素为线性表的线性表（ F ）。评卷人得分三、单项选择题（60小题，共30分）1若需在的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 A、快速排序 B、堆排序 C、归并排序 D、直接插入排序 3在采用链接法处理冲突的开散列表上，假定装填因子的值为4，则查找任一元素的平均查找长度为 A、3 B、 35 C、 4 D、 254设散列表的长m=14，散列函数为h(k)=k11，表中已有4个记录(如图所示)，如果采用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是 A、 8 B、 3 C、 5 D、 95若根据查找表建立长度为m的闭散列表并采用二次探测处理冲突，假定对一个元素第一次计算的散列地址为d，则第4次计算的散列地址为 A、(d+l)m B、(d-1)m C、(d+4)m D、(d-4)m6对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分在第l趟划分过程中，元素移动次数最多的是序列 A、70，75，82，90, 23, 16，10，68 B、70，75，68，23，10，16，90，82 C、82，75，70，16，10，90，68，23 D、23，10，16，70，82，75，68, 907已知待排序的n个元素可分为nk个组，每个组包含k个元素，且任一组内的各元素均分别大于前组内的所有元素和小于后组内的所有元素，若采用基于比较的排序，其时间下界应为 A、 B、 C、 D、8若对一个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂性为 A、O(l) B、 C、 D、9在对一个元素进行直接选择排序过程中，第i趟需从（ ）个元素中选择出最小值元素。 A、n-i+1 B、n-i C、 i D、i+110快速排序（ ）在情况下不利于发挥其长处。 A、待排序数据量太大 B、待排序数据相同值过多 C、待排序数据已基本有序 D、待排序数据值差过大11在一个有n个顶点的无向图中，有O()条边，则应该选用（ ）算法来求这个网的最小生成树，从而使计算时间较少。 A 、PRIM B、 KRUSKAL12用DFS遍历一个无环有向图，并载DFS算法退栈返回时打印出相应得顶点，则输出的顶点序列是 A、逆拓扑有序的 B、拓扑有序的 C、无序的13散列函数有有一 个共同性质，即函数值应按_取其值域的每一个值。 A、最大概率 B、最小概率C、同等概率 D、平均概率14对稀疏矩阵进行压缩存储目的是 A、便于进行矩阵运算 B、便于输入和输出 C、节省存储空间 D、降低运算的时间复杂度15对文件进行直接存取的依据是 A、按逻辑记录号去存取某个记录 B、拄逻辑记录的关键字去存取某个记录 C、按逻辑记录的结构去存取某个记录 D、按逻辑已录的具体内容去存取某个记录16对散列文件，以下说法错误的是 A、散列文件插入、删除方便，不需要索引区且节省存储空间 B、散列文件只能按关键字随机存取且存取速度快 C、经过多次插入、删除后，可能出现溢出桶满而基桶内多数记录已被删除的情况 D、散列文件顺序存取方便18在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫 A、插入排序 B、枚举排序 C、选择排序 D、交换排序19对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 A. 选择 B、 冒泡 C、 快速 D、 插入20有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。 A、下面的B，C，D都不对。 B、9，7，8，4，-1，7，15，20 C、20，15，8，9，7，-1，4，7 D、 9，4，7，8，7，-1，15，2021一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。 A、(38,40,46,56,79,84) B、 (40,38,46,79,56,84) C、(40,38,46,56,79,84) D、 (40,38,46,84,56,79)22下面给出的四种排序法中( )排序法是不稳定性排序法。 A、 插入 B、 冒泡 C、 二路归并 D、 堆积23在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。 A、n/2 B、n/2 -1 C、1 D、n/2 +2 24 就平均性能而言，目前最好的内排序方法是( )排序法。 A. 冒泡 B、 希尔插入 C、 交换 D、 快速 25 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是 A 6 B、 4 C、 3 D、 226栈和队都是 A、顺序存储的线性结构 B、 链式存储的非线性结构 C、 限制存取点的线性结构 D、 限制存取点的非线性结构27栈和队列的共同点是 A、 都是先进先出 B、 都是先进后出 C、 只允许在端点处插入和删除元素 D、 没有共同点28假定一个顺序循环队列存储于数组An中，其队首和队尾指针分别用front和rear表示，则判断队满的条件是 A、(rcar-1)n=front B、(rear+1)n=front C、rear =(front-1)n D、rear =(front+1)n29栈在（ ）中应用。 A、 递归调用 B、 子程序调用 C、 表达式求值 D、 A，30 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是 A、XYZ B、 YZX C、 ZXY D、 ZYX31 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是 A、 i-j-1 B、 i-j C、 j-i+1 D、 不确定的32在下面的程序段中，对x的赋值语句的频度为 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A、 O(2n) B、O(n) C、O(n2) D、O() 33以下那一个术语与数据的存储结构无关？ A、栈 B、 哈希表 C、线索树 D、 双向链表34一个算法应该是 A、程序 B、问题求解步骤的描述 C、要满足五个基本特性 D、A和C35线性表（ a1,a2,an）以链接方式存储时，访问第i位置元素的时间复杂性为 A、O（i） B、O（1） C、O（n） D、O（i-1）36线性表的表元存储方式有(（1）)和链接两种。试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。表左的s指向起始表元。 表元编号货号数量表元间联系1 618 40 2 2 205 2 3 3 103 15 4 4 501 20 5 5 781 17 6 6 910 24 0表元编号货号数量表元间联系 1 618 40 5 2 205 2 1 3 103 15 4 4 501 20 2 5 781 17 6 6 910 24 3表元编号货号数量表元间联系 1 618 40 5 2 205 2 13 103 15 4 4 501 20 0 5 781 17 6 6 910 24 3表元编号货号数量表元间联系 1 2 1 618 40 5 2 2 205 2 1 0 3 103 15 4 6 4 501 20 0 3 5 781 17 6 1 6 910 24 3 5供选择的答案： A、连续 B、单向链接 C、双向链接 D、不连接 E、循环链接 F、树状 G、网状 H、随机 I、顺序 J、顺序循环37在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，其修改指针的操作是_ A、 B、 C、 D、38若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A、顺序表 B、双链表 C、带头结点的双循环链表 D、单循环链表39在下列3种次序的线索二叉树中（ ）对查找指定结点在该次序下的后继效果较差。 A、前序线索树 B、中序线索树 C、后序线索树40 遍历仍需要栈支持的 A、前序线索树 B、中序线索树 C、后序线豢树41设F是森林，B是由F变换得到的二叉树。若F中有N个非终端结点，则B中右指针域为空的结点有_个。 A、 N - l B、N C、N+1 D、N+242数组SZ-350，O 10含有元素数目为 A、88 B、 99 C、 80 D、 9043已知串S=aaab，其next数组值为 A、0123 B、1123 C、1231 D、121144已知Head(Tail(Head(S), Head(Tail(Tail(S)=a,广义表S满足上式，则S为_.(其中，方括号表示广义表，圆括号表示函数。如a,b)表示由a,b构成的广义表，而Head()表示取广义表的头部。) A、a,b,b,a B、b,a,a,b C、 a,a,b,b D、b,a,a,b E、a,b,b,a F 、b,b,a,a45设有一个10阶的对称矩阵A，采用压缩破除计方式，以行序为主存储，a1,1为第一个元素，其存储地址为1，每个元素占1个地址空间，则a8,5的地址为。 A、13 B、33 C、18 D、4046串是一中特殊的线性表，其特殊性体现在。 A、 可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、 数据元素可以是多个字符47下列说法正确的是。 A、 线性表的逻辑顺序与存储顺序总是一致的 B、 线性报第链式存储结构中，内存中可用的存储单元可以使连续的，也可以不连续 C、 线性表弟顺序存储结构优于链式存储结构 D、 每种数据结构都具有插入、删除和查找三种基本运算 48在一个具有 n 个结点的有序单链表中插入一个新结点，并使插入结点后的单链表仍然有序，则该操作的时间复杂性量级为。 A、.0 （ 1 ） B、 0 （ n ） C、 0 （ nlog2n ） D、 0 （ n2 ） 49 P 和 q 两个指针分别指向双向循环链表 L 两个元素， p 所指元素是 q 所指元素的后继的条件是。 A 、p =q B 、Q-next=p C、 p-next=q D、 q-next=p-next 50深度为h的满二叉树的第i层有（ ）个结点。（ih） A、2i-1 B、 2i-1 C、2h-1 D、2h-151 顺序栈是空栈的条件是。 A、 top=0 B、 top=1 C、 top=-1 D、 top=m 52算法能正确地实现预定功能的特性称为。 A、 正确性 B、 易读性 C、 健壮 D、 高效率 53某二叉树的前序遍历结点访问顺序为， ABDGCDFH中序遍历结点访问顺序为DGBAECHE，则其后续遍历结点访问顺序为。 A、 BDGCEFHA B、 GDBECFHA C、 BDGAECHF D、 GDBDHFCA 54某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是： A、E,G,F,A,C,D,B B、E,A,C,B,D,G,F C、E,A,G,C,F,B,D D、上面的都不对 55下面的说法中正确的是.（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；（2）按二叉树定义，具有三个结点的二叉树共有6种。 A、(1)(2) B、(1) C、(2) D、(1)、(2)都错 56利用二叉链表存储树，则根结点的右指针是 A、指向最左孩子 B、指向最右孩子 C、空 D、非空57 下面关于B和B+树的叙述中，不正确的是 A、 B树和B+树都是平衡的多叉树。 B、 B树和B+树都可用于文件的索引结构。 C、 B树和B+树都能有效地支持顺序检索。 D、 B树和B+树都能有效地支持随机检索。58既希望较快的查找又便于线性表动态变化的查找方法是 A、顺序查找 B、 折半查找 C、 索引顺序查找 D、 哈希法查找59设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作 A、s-link=p-link; p-link=s; B、q-link=s; s-link=p C、p-link=s-link;s-link=p; D、p-link=s; s-link=q;60ISAM文件和VASM文件属于 A、 索引非顺序文件 B、 索引顺序文件 C、 顺序文件 D、 散列文件评卷人得分四、算法设计题（2小题，共4分）1试设计一个算法, 使得在O(n)的时间内重排数组, 将所有取负值的排序码排在所有取正值(非负值)的排序码之前。2试给出二叉树的自下而上、自右而左的层次遍历算法。评卷人得分五、填空题（40小题，共20分）1设有两个散列函数H1(K)=K%13和H2(K)=K11+1，散列表为T0. 12，用双重散列解决冲突。函数Hl用来计算散列地址，当发生冲突时，H2作为计算下一个探测地址增量，假定在某时刻表T的状态如图所示。下一个被插入的关键字是42，则其插人的位置是_。2克鲁斯卡尔算法的时间复杂度为_，它对_图较为适台。3分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。 4PROC sift(VAR r：listtype;k,m:integer); 假设rk+1.m中各元素满足堆的性质，本算法调整rk使整个序列rk.m中各元素满足堆的性质。i:=k; j:= (1)_; x:=rk.key; finished:=false; t:=rk;WHILE (j=m) AND NOT finished DO IF(jm) AND (2)_) THEN j:=j+1; IF x0 DO insert(head,num); read(num) ENDP; 10队列是特殊的线性表，其特殊性在于_。11表达式求值是_应用的一个典型例子。12带头结点的双循环链表L中只有一个元素结点的条件是：_13已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_14对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _个，单链表为_个。15在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：s .next:=p； s .prior:= _；p .prior:=s；_:=s；16在单链表中设置头结点的作用是_。17在单链表中设置头结点的作用是_。18顺序存储结构使线性表中逻辑上相邻的数据元素在物理位胃上也相邻。因此，这种表便于_访问，是一种_结构。19深度为k（设根的层数为1)的完全二叉树至少有_个结点，至多有_个结点k和结点数n之间的关系足_.20已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_。21设循环队列存放在向量sq.data0:M中，则队头指针sq.front在循环意义下的出队操作可表示为_，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_。 22广义表的元素可以是广义表；因此，广义表是一个_的结构。23设有一个10阶对称矩阵A采用压缩存储方式(以行为主序存储：1)则的地址为_。24空串与空格串的医别在于_。25下面程序段的时间复杂度为_。(n1) sum=1； for (i=0;sumn;i+)