数据结构复习题及答案(12级)

一、选择题。(每题2分,共4分)(1) 计算机辨认.存储和加工解决的对象被统称为_。A.数据 B.数据元素 C.数据构造 .数据类型(2) 数据构造一般是研究数据的_A _及它们之间的联系。A.存储和逻辑构造 B.存储和抽象C.抱负和抽象 D.抱负与逻辑(3)不是数据的逻辑构造是_ A _。A.散列构造 线性构造 C.树构造 D.图构造 (） 数据构造被形式地定义为,其中D是_B _的有限集,R是_C_的有限集。A.算法 B数据元素 C.数据操作 D.逻辑构造() 构成数据的基本单位是_ _。 .数据项 B.数据类型数据元素 .数据变量(6) 设数据构造A(D，R）,其中D=1，2,3，4,=r,r，,，nxt；pnext=-s;B q-next=s; -ext=p;C. p-nex=s-ext；-xt=；D. p-ext=s;s-next=q;() 设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为_ A _。A. -net=p-etet . p=p-nextC.p=p-ext-ne D. -netp(18） 下列说法哪个对的？_ D _. 堆栈是在两端操作、先进后出的线性表.堆栈是在一端操作、先进先出的线性表C 队列是在一端操作、先进先出的线性表D. 队列是在两端操作、先进先出的线性表(1) 栈和队列的共同点是_ C_。A. 都是先进后出 . 都是先进先出. 只容许在端点处插入和删除元素 D. 没有共同点(20） 栈与一般线性表的区别重要在_。A、元素个数 B、元素类型 、逻辑构造 D、插入、删除元素的位置(2) 链栈与顺序栈相比,比较明显的长处是_D_。A、插入操作更加以便B、删除操作更加以便C、不会浮现下溢的状况 D、不会浮现上溢的状况(22） 如下数据构造中哪一种是非线性构造_D _。.队列B栈C.线性表D.二叉树(23） 若已知一种栈的入栈序列是，,，n，其输出序列为1，p2,p,pn，若p1=,则pi为_ C _。A. iB. niC. -i+1D.不拟定（24) 当运用大小为N的一维数组顺序存储一种栈时，假定用top=表达栈空，则向这个栈插入一种元素时，一方面应执行_ B _语句修改to指针。A. to+ B. to- C. to=0D.to（25) 个元素进栈的顺序是A,B,C,D，经运算P()后，栈顶元素是_ C_。A. AB. C. CD. D() 一种栈的输入序列是,b,e，则栈的不也许的输出序列是_ _。A. dcaB decbaC. dceaD. acde(27) 设输入序列是、3、n,通过栈的作用后输出序列的第一种元素是n,则输出序列中第i个输出元素是_ _。A. -iB. n-1i +1-iD.不能拟定（2) 字符A、B、C、D依次进入一种栈，按出栈的先后顺序构成不同的字符串，至多可以构成_ _个不同的字符串？. B1C1D. 21(2) 设指针变量op指向目前链式栈的栈顶，则删除栈顶元素的操作序列为_ D _。A to=top1; . p=top-; C. top-ext=top; D toptop-nxt; (0）设栈S和队列Q的初始状态为空,元素E、E2、E3、E4、E5和E依次通过栈S,一种元素出栈后即进入队列,若个元素出列的顺序为E2、4、3、E6、E5和E,则栈的容量至少应当是_ C _。. 6B. 4C.3D.2(31) 若用一种大小为6的数组来实现循环队列,且目前rear和frot的值分别为和。当从队列中删除一种元素，再加入两个元素后,rear和on的值分别为_ B _。A. 1和5B. 2和4C. 4和2D 5和1(3） 设顺序循环队列0:-1的头指针和尾指针分别为和，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的目前位置，则该循环队列中的元素个数为_C _。A. R-.F-RC. （-F+M)%M （FR+M)M(33) 设指针变量frot表达链式队列的队头指针，指针变量ra表达链式队列的队尾指针，指针变量指向将要入队列的结点,则入队列的操作序列为_ _。A.ron-next=s；frnt=；B. s-net=rer;rr=s；C.rea-net=s；rer=s;D s-nx=fron；frot=s;(34) 如下陈述中对的的是_ A _。A.串是一种特殊的线性表B 串的长度必须不小于零C.串中元素只能是字母D. 空串就是空白串(35） 下列有关串的论述中,对的的是_ _。A 串长度是指串中不同字符的个数B. 串是n个字母的有限序列C 如果两个串具有相似的字符，则它们相等D. 只有当两个串的长度相等,并且各个相应位置的字符都相符时才相等(6) 字符串的长度是指_ _。A.串中不同字符的个数B 串中不同字母的个数C. 串中所含字符的个数D. 串中不同数字的个数(37) 两个字符串相等的充要条件是_ _。A. 两个字符串的长度相等B两个字符串中相应位置上的字符相等C. 同步具有(A)和()两个条件 D. 以上答案都不对(38) 串是一种特殊的线性表,其特殊性体目前_B _。A.可以顺序存储B 数据元素是一种字符C. 可以链接存储. 数据元素可以是多种字符（39) 设有两个串和,求在p中初次浮现的位置的运算称作_ _。. 连接B. 模式匹配. 求子串. 求串长(40) 设串sIABEFG,s=PQRST,函数co(x,y）返回和y串的连接串，sb(,i,j)返回串的从序号i的字符开始的个字符构成的子串,ln(s）返回串s的长度，则on(ubs(s1，2,1en(s)），subs（sl,ln(s2）,2)的成果串是_ D _。. BCDEFB.EFGC. CQRSTD. BCDEFEF(1) 函数subsr(“DATATUCTURE”,5，9）的返回值为_ _。A. “STRCTURE”B. “DATA”C “ASRUCTU” . “DATASTRUCTURE”(4） 设串S=”I AM TECHR!”,其长度是_ _。1B11C. 14D. （3) 假定在一棵二叉树中，双分支结点数为15个,单分支结点数为个,则叶子结点数为_B_。 A. 1 B16 C. 17 D 7（44) 假定一棵二叉树的结点数为18个,则它的最小高度_B_。. 4 B. 5 . 6 . 18(4） 在一棵二叉树中第五层上的结点数最多为_C_。A8 B. 15 C.6 （46) 在一棵具有五层的满二叉树中，结点总数为_A_。. 31 B 32 C. 3 D 16(47) 已知8个数据元素为（34、76、45、18、26、4、9、5），按照依次插入结点的措施生成一棵二叉排序树后，最后两层上的结点总数为_B_。. 1 B C. D. 4(48) 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树,该树的带权途径长度为_C_。 A. 2 B37 C.44 D. 46(49) 在树中除根结点外，其他结点提成m ()个_ _的集合T,T2,T3.Tm，每个集合又都是树，此时结点称为T的父结点,Ti称为T的子结点（1im)。A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交(50) 如果结点A有三个兄弟，并且B是A的双亲，则B的出度是_B_。A. B. 4 C. 5 D. 1(51) 在一种有向图中,所有顶点的入度之和等于所有顶点的出度之和的_B_倍。A.2 B 1 C. 2 .(5) 具有n个顶点的无向完全图,边的总数为_D_条。An B.n C. +1 n*（n1）/2（53) 在无向图的邻接矩阵A中,若A,j等于1，则j,等于_C _。A +j B. i-j C. 1 D. 0(5) 图的深度优先或广度优先遍历的空间复杂性均为_A_。(访问标志位数组空间)A. () BO（e) C. O(n-e) D. O(n+e)(5） 请指出在顺序表、5、0、14、1、18、3、35、41、52中,用折半法查找核心码需做_次核心码比较。A.2 .3 C D(56) 对线性表进行折半查找时，必须规定线性表 _ C _。A以顺序方式存储 B 以链接方式存储C. 以顺序方式存储,且结点按核心字有序排列D. 以链接方式存储,且结点按核心字有序排列(57) 设二叉排序树中有n个结点,则在二叉排序树的平均查找长度为_ B _。A（） . O(ln) . O(n) D. O(n)(5) 依次插入序列(50,72，3，85,75,20，5,45,65，30)后建立的二叉搜索树中,查找元素5要进行_ A _元素间的比较。A.4次.5次.7次D.1次（59) 设散列表中有个存储单元,散列函数H(k)= key %p,则p最佳选择_ _。A 不不小于等于m的最大奇数. 不不小于等于的最大素数C 不不小于等于m的最大偶数D. 不不小于等于的最大合数（6) _ D _是HASH查找的冲突解决措施。A.求余法 B. 平方取中法 C. 二分法 D 开放地址法(6) 当的值较小时,散列存储一般比其她存储方式具有_ B_的查找速度。A. 较慢.较快C. 相似 不拟定(62) 对线性表进行折半查找最以便的存储构造是_ B _。A.顺序表 B.有序的顺序表C链表 D有序的链表（3） 如果规定一种线性表既能较快的查找,又能适应动态变化的规定,可以采用_ D_查找措施。A.分块 .顺序 折半 D散列（64) 散列函数有一种共同性质,即函数值应按_C _取其值域的每一种值。最大概率 B最小概率 .同等概率 平均概率(6) 下述排序算法中,稳定的是_ B_。A直接选择排序 B. 直接插入排序 C迅速排序 D.堆排序 (66)下列排序算法中,_ A_需要的辅助存储空间最大。A.迅速排序B.插入排序C.希尔排序D.基数排序（7) 下列多种排序算法中平均时间复杂度为（n2)是_D _。A 迅速排序 B 堆排序 C.归并排序 D.冒泡排序(8） 在基于核心码比较的排序算法中，_ C_算法在最坏状况下,核心码比较次数不高于(nlg2n)。A. 起泡排序. 直接插入排序. 二路归并排序D.迅速排序(69) 一组记录为46,79,56，38,8，40,则采用冒泡排序法按升序排列时第一趟排序成果是_ B _ 。A.6,79,56，38,40,84 B.6,5,38,79，4,4C3,40，46,56,，79 D.38,4，7，6，0,(7） 每次从无序表中取出一种元素，把它插入到有序表中的合适位置，此种排序措施叫做_ A _ 排序。A 插入 B.堆 C.迅速 D归并(71） 每次从无序表中挑选出一种最小或最大元素,把它互换到有序表的一端，此种排序措施叫做_ B _排序。A.插入 B. 堆 C.迅速 .归并(2) 设一组初始记录核心字序列(，6,3，)，以第一种记录核心字5为基准进行一趟迅速排序的成果为_ C _。A.2，8,B. 3，2，5,8，6C ,5，6,8D. 2，,，5，8（7） 下列排序措施中，哪一种措施的比较次数与纪录的初始排列状态无关_ D _。A. 直接插入排序 B 起泡排序C. 迅速排序 . 直接选择排序(4）设有核心码初始序列Q，H，C,Y,P，A，M,R,D,F,X，新序列，,C,D，P,A，Q,R,Y,X是采用_ 措施对初始序列进行第一趟扫描的成果。. 直接插入排序 B.二路归并排序.以第一元素为分界元素的迅速排序 基数排序（5） 在待排序文献已基本有序的前提下，下述排序措施中效率最高的是_ C _。A 直接插入排序 B. 直接选择排序C. 迅速排序 D 归并排序（6)若需在O(nlg)的时间内完毕对数组的排序，且规定排序是稳定的，则可选排序措施是_ _ 。. 迅速排序 堆排序C 归并排序 D. 直接插入排序(77) 将两个各有n个元素的有序表归并成一种有序表,其至少的比较次数是_B_。A. n B. 2n-1 C. 2n D. n-1(8) 下列排序算法中,_ _算法也许会浮现下面状况：初始数据有序时,耗费的间反而最多。A. 堆排序 B冒泡排序 C.迅速排序 D. SHELL排序二、填空题。（每空1分，共1分）(1) 数据构造是一门研究非数值计算的程序设计问题中计算机的 数据 以及它们之间的 关系 和运算等的学科。()数据构造涉及数据的逻辑构造构造和物理构造构造。（3）数据构造从逻辑上划分为三种基本类型：_线性数据构造_、_树型构造_和_图构造_。() 数据的物理构造被分为_顺序存储_、_链式存储_、_索引存储_和_散列表（Has）存储_四种。（) 一种抽象数据类型涉及_变量的取值范畴_和 _操作的类别_两个部分。(6)数据的逻辑构造是指 数据元素间的逻辑关系 ,数据的存储构造是指 数据元素存储方式或者数据元素的物理关系 。(7) 数据构造是指数据及其互相之间的_关系_。当结点之间存在对（M：N）的联系时，称这种构造为_网状构造_。当结点之间存在对N（1:N）的联系时，称这种构造为_树构造_。（8)对算法从时间和空间两方面进行度量,分别称为 空间复杂度和时间复杂度 分析。(9) 算法的效率可分为_空间_效率和_时间_效率。(10） fo（i，t1，=;i1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点?多少个分支结点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点？答:结点个数为n时,高度最小的树的高度为,有两层，它有-1个叶结点，1个分支结点;高度最大的树的高度为-，有n层，它有1个叶结点,n-个分支结点。2.什么是内部排序?什么是排序措施的稳定性?答:假定给定具有n个记录的文献(r1,2，rn）,其相应的核心字为（1，k)，则排序就是拟定文献的一种序列r,r,，rn,使得1k2kn，从而使得文献中n个记录按其相应核心字有序排列。如果整个排序过程在内存中进行,则排序叫内部排序。假设在待排序的文献中存在两个或两个以上的记录具有相似的核心字,若采用某种排序措施后,使得这些具有相似核心字的记录在排序前后相对顺序仍然保持不变，则觉得该排序措施是稳定的，否则就觉得排序措施是不稳定的。五、分析题。(每题4分，共分）. 分析下面语句段执行的时间复杂度。 (1）for（=;i=；i+) for(j1；jn;+） s+;（2) o(i=1；in;+) for(=i;n;j+)s+；(） fo（=1;i=n;i+） f(j1；j=;j+) s；(）1； =0；wile(i=n-1)k+=10*i；i+；（5) for (i1；in;i+) for(j;=i ；+) for(k=1;kj；k+) x；（1) (n2） (2） (n2) (3) (2） （) （n-1) () (n3）2.写出下列程序段的运营成果（栈中的元素类型是char):in( ) eStac s,p;chrx,y;p=&;InitQeue（p);= c; y= k；sh (p，）; ush (,a）；ush (p，y);x=o(p）;push (p，）; push (p,x)；x=pop (p)；ph （p，s）；whil (!EmptySetack(p）) yp(p）; pritf(“%c”，y)；nf（“%c”，x）; 答：sta. 写出下列程序段的运营成果(队列中的元素类型是cha):ain( ) eQuu , q；char x，y;=&a;x=; yc;Init_uu(q)；InQu(q,); n_Queue(q,r)； _eu(q, y);xOut_Quee （）;Iueue（q,x);= Out_Queue (q);In_eu（q,a ）;whil (！Emy_qSack(q)） y Out_eue(q）; pritf(“%”,y)；printf(“%Cn”,)；答:char