还剩6页未读，继续阅读
文本内容:
第一章绪论.从逻辑上可以把数据结构分为..两大类1动态结构、静态结构顺序结构、链式结构A.B.线性结构、非线性结构初等结构、构造型结构C.D..在下面的程序段中，对的赋值语句的频度为..2xFor k=l；k=n；k++For j=l;j=n；j++；x=x+1A.02n B.0n C.0n2D.Olog2n.采用顺序存储结构表示数据时，相邻的数据元素的存储地址.•3一定连续一定不连续A.B.不一定连续部分连续、部分不连续C.D..下面关于算法的说法，正确的是4算法的时间复杂度一般与算法的空间复杂度成正比A.解决某问题的算法可能有多种，但肯定采用相同的数据结构B.算法的可行性是指算法的指令不能有二义性C.同一个算法，实现语言的级别越高，执行效率就越低D..在发生非法操作时，算法能够作出适当处理的特性称为正确性健壮性可读5A.B.C.性可移植性D.第二章线性表.线性表是1・・一个有限序列，可以为空一个有限序列，不能为空一个无限序列，可以为空一A.B.C.D.个无限序列，不能为空对顺序存储的线性表，设其长度为在任何位置上插入或删除操作都是等概率的
2.n,插入一个元素时平均要移动表中的个元素A.n/2B.n+l/2C.n-1/2D.n线性表采用链式存储时，其地址
3.o必须是连续的部分地址必须是连续的A.B.一定是不连续的连续与否均可以C.D.用链表表示线性表的优点是
4.便于随机存取花费的存储空间较顺序存储少A.B.便于插入和删除数据元素的物理顺序与逻辑顺序相同C.D..链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则5采用存储方式最节省运算时间单链表双链表单循环链表带头结点的双向循环链表A.B.C.D.下面关于线性表的叙述，错误的是（）
6.o线性表采用顺序存储，必须占用一片地址连续的单元A.线性表采用顺序存储，便于进行插入和删除操作B.线性表采用链式存储，不必占用一片地址连续的单元C.线性表采用链式存储，不便于进行插入和删除操作D.单链表中，增加一个头结点的目的是为了（）
7.使单链表至少有一个结点标识表结点中首结点的位置A.B.方便运算的实现说明单链表是线性表的链式存储C.D.在单链表指针为的结点之后插入指针为结点，正确的操作是（）
8.p s0A.p-next=s；s-next=p-next；；；B.s-next=p-next p-next=sC.p-next=s；p-next=s-next；D.p-next=s-next；p-next=s；在双向链表存储结构中，删除所指的结点时须修改指针
9.pA.p-prior-next=p-next;p-next-prior=p-prior;B.p-prior=p-prior-prior;p-prior-next=p;C.p-next-prior=p;p-rlink=p-next-next;D.p-next=p-prior-prior;p-prior=p-next-next.完成在双向循环链表结点之后插入的操作是10p sA.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.p-next-prior=s;p-next=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;.若某线性表中最常用的操作是取第个元素和找第个元素的前趋元素，则采用.11i i・存储方式最节省运算时间单链表顺序表双向链表单循环链表A.B.C.D..若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元12素，则采用.存储方式最节省运算时间・单链表仅有头指针的单循环链表A.B.双向链表仅有尾指针的单循环链表C.D.第三章栈和队列13向一个栈顶指针为top的链栈中插入一个P所指结点时，其操作步骤为（）O；；；A.top-next=p B.p-next=top-next top-next=pC.p-next=top；top=p；D.p-next=top；top=top-next；对于栈操作数据的原则是（14先进先出后进先出A.B.后进后出不分顺序C.D.15若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为pl,p2,p3,…，pn,若pn是n,则为（）Pi不确定A.i B.n-i C.n-i+1D.表达式（）的后缀表达式是（）
4.a*b—c+dA.abed*—P B.abc—*d+C.abc*—d+D.H—*abcd
5.采用顺序存储的两个栈的共享空间S[Lm],用top[i]代表第i个栈（i=l,2）的栈顶，栈的底在栈的底在则栈满的条件是（）1S[l],2S[m],A.top
[2]—top[l]=0B.top[l]+1=top
[2]C.top[l]+top
[2]=m D.top[l]=top
[2]一个栈的入栈序列是则栈的不可能的输出序列是（）
6.a,b,c,d,e,A.edeba B.decba C.deeab D.abede在一个链队列中，若、分别为队首、队尾指针，则插入所指结点的操作为
7.f rp（）OA.f-next=p；f=p B.r-next=p；r=pC.p-next=r；r=p D.p-next=f；f=p用不带头结点的单链表存储队列时，在进行删除运算时（）
8.仅修改头指针仅修改尾指针A.B.头、尾指针都要修改头、尾指针可能都要修改C D..递归过程或函数调用时，处理参数及返回地址，要用一种称为..）的数据结构9队列静态链表栈顺序表A.B.C.D..栈和队都是）1・・顺序存储的线性结构链式存储的非线性结构A.B.限制存取点的线性结构限制存取点的非线性结构C.D.第四章字符串及线性结构的扩展下面关于串的叙述，错误的是.）L・串是字符的有限序列A.串既可以采用顺序存储，也可以采用链式存储B.空串是由空格构成的串C.模式匹配是串的一种重要运算D..串的长度是指2串中所含不同字母的个数串中所含字符的个数A.B.串中所含不同字符的个数串中所含非空格字符的个数C.D.
3..二维数组的成员是个字符（每个字符占一个存储单元，即一个字节）组成的串，4M6行下标i的范围从到8,列下标j的范围从1到10,则存放M至少需要
（1）..）个字节；M的第8列和第5行共占
（2）..）个字节；若M按行优先方式存储，元素M⑻⑶的起始地址与当M按列优先方式存储时的
（3）..）元素的起始地址一致（）1A.
9..B.
18..C.
24..D.540（）2A.
10..B.ll..C.
5..D.60（）3A.M
[8][
5..B.M
[3][
10..C.M
[5][
8..D.M
[0]
[9].数组中，每个元素的存储占个单元，行下标从到列下标从至从首5A3i18,j1U10,地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是
（1）..）；若该数组按行存放，元素A
[8]
[5]的起始地址为
（2）..）；若该数组按列存放，元素A
[8]
[5]的起始地址为
（3）..）□（）1A.
8..B.
10..C.
24..D.270（）2A.SA+
14..B.SA+
14..C.SA+
22..D,SA+225（）3A,SA+
14..B.SA+
18..C.SA+
11..D.SA+
225.稀疏矩阵采用压缩存储，一般有..）两种方法6二维数组和三维数组三元组和散列A.B.三元组表和十字链表散列和十字链表C.D.第五章树结构.下列说法正确的是.）1・二叉树中任何一个结点的度都为二叉树的度为A.2B.2一棵二叉树的度可小于任何一棵二叉树中至少有一个结点的度为C.2D.
22.以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n0）,空链域的个数为.）・A.2n-l B.n-1C.n+1D.2n+l.线索化二叉树中，某结点*没有孩子的充要条件是3p且A.p-lchild=NUL..B.p-ltag=l p-rtag=lC.p-ltag=・・・・・D.p-〉lchild二NULL且p-ltag=l.如果结点有个兄弟，而且是的双亲，则的度是4A3B ABA.3B.4C.5D.
1.某二叉树有个结点，设按某种顺序对中的每个结点进行编号，编号值为5T nT1,且有如下性质中任意结点其编号等于左子树上的最小编号减而的右子树2,…,n,T v,1,v的结点中，其最小编号等于左子树上结点的最大编号加这是按.）编号的中序遍v1,・A.历序…先序遍历序…后序遍历序…层次顺序B.C D..设是一个森林,是由转换得到的二叉树,中有个非终端结点,中右指针域6F BF Fn B为空的结点有.）个・A.n—1B.n C.n+1D.n+
2.一棵完全二叉树上有个结点，其中叶子结点的个数是..）71001A.500B.501C.490D.
495.设森林中有棵树，第.第和第棵树的结点个数分别为和与森8F3123Nl,N2N3林对应的二叉树根结点的右子树上的结点个数是.）F・A.N1B.N1+N2C.N2D.N2+N
3.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序9不发生改….发生改…不能确….以上都不对A..B C..D.若一棵二叉树的后序遍历序列为中序遍历序列为则先序遍历序列为10dabec,debac,・）・A.cbe...B.deca...C.deab...D.cedba.若一棵二叉树的先序遍历序列为中序遍历的序列为则后序遍历11abdgcefh,dgbaechf,的结果为.）・A.gcefh..B.gdbecfh..C.bdgaech..D.gdbehfca.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足
12.）・o所有的结点均无左孩.所有的结点均无右孩子A.・B.只有一个叶子结….是一棵满二叉树C.D..设高度为的二叉树上只有度为和度为的结点，则此类二叉树中所包含的结点13h02数至少为.）・A・
2.・B・2h—・.C.2h+..D.h+l.一个具有个结点的二叉树的高为14567h之..之间A...B.I..C.9〜566D.10〜567第六章图结构条边的无向图的邻接表的存储中，边结点的个数有LnA…B.
2..C.n/..D.nXn条边的无向图的邻接多重表的存储中，边结点的个数有
2.nA...B.
2..C.n/..D.nXn.下列哪一种图的邻接矩阵是对称矩阵？..）3有向.无向..网A.・B.C.AOV..D.AOE.最短路径的生成算法可用4普利姆算..克鲁斯卡尔算..迪杰斯特拉算哈夫曼算法A.B.C・・D..一个无向图的邻接表如下图所示5序号vertex firstedge
（1）从顶点vO出发进行深度优先搜索，经历的结点顺序为（）oA.vO,v3,v2,v..B.vO,vl,v2,v3C.vO,v2,vl,v..D.vO,vl,v3,v2
（2）从顶点vO出发进行广度优先搜索，经历的结点顺序为（）oA.vO,v3,v2,v..B.vO,vl,v2,v3C.vO,v2,vl,v..D.vO,vl,v3,v
2.设有向图个顶点和条边，进行拓扑排序时，总的计算时间为•.）6n e（（（（）A.O nlog2e..B.O eXn..C.O elog2n..D.O n+e.含有个顶点条边的无向连通图，利用算法生成最小生成树，其时间复杂7n eKruskal度为）・・（（（（）A.O elog2e..B.O eXn..C.O elog2n..D.O nlog2n.关键路径是事件结点网络中8从源点到汇点的最长路..从源点到汇点的最短路径A.B.最长的回…..…最短的回路C D..下面关于求关键路径的说法，不正确的是9求关键路径是以拓扑排序为基础的A.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同B.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续C.时间的差关键活动一定位于关键路径上D..有个结点的无向图至少有..）条边才能确保其是连通图1010A…B…C・第七章查找静态查找表与动态查找表的根本区别在丁.）
1.・它们的逻辑结构不一.•…施加在其上的操作不一样A.B.所包含的数据元素类型不一..存储实现不一样C.D..在表长为的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为）2n・・A…B...C.n+..D.n-
1.顺序查找适用于存储结构为.的线性表3・散列存.压缩存储A.・B.顺序存储或链式存.索引存储C.・D..用顺序查找法对具有个结点的线性表查找一个结点的时间复杂度为4nA.Olog2n
2..B.Onlog2n..C.On..D.Olog2n.适用于折半查找的表的存储方式及元素排列要求为5链接方式存储，元素无序A.链接方式存储，元素有序
8.顺序方式存储，元素无序C顺序方式存储，元素有序D..有一个长度为的有序表，按折半查找法对该表进行查找，在表内各元素等概率情912况下查找成功所需的平均比较次数为.・A.35/
1..B.37/
1..C.39/
1..D.43/12在有序表｛｝上进行折半查找关键字为的数101,3,9,12,32,41,62,75,77,82,95,10082据元素需要比较..次A…B...C...D.5设散列表长为散列函数为当前表中已有个结点1114,H key.ke..ll4o如用二次探测再散列处理冲突，则addr15=4,addr38=5,addr61=6,addr84=7关键字为的结点的地址是49oA…B...C...D.9散列函数有一个共同的性质，即函数值应当以•.取其值域的每个值12最大概.最小概.平均概.同等概率A.・B.・C.・D..假定有个关键字互为同义词，若用线性探测法把这个关键字存入散列表中,至13k k少要进行.次探测・次A.k-
1..B.k..C.k+
1..D.k k+1/
2.在散列函数中，一般来讲,应取.14H k...m m・奇.偶素.充分大的数A.・B.・・C・D..在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置,在15查找成功的情况下，所探测到的这些位置上的键值一定是同义…一定不是同义词A.B.都相…….不一定都是同义词C.D第八章排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是.
1.・插入排..选择排.快速排.归并排序A.B.・C.・・D.设有个无序的元素，希望用最快的速度挑选出其中前个最大的元素，最好2100010选用.排序法・冒泡排.快速排.堆排.基数排序A.・B.・C.・D..具有个记录的序列，采用冒泡排序最少的比较次数是312A...B.
14..C.I..D.
66.下列四种排序方法中，要求内存容量最大的是4插入排..选择排..快速排•.归并排序A.B.C.D..初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为•.5A.n..B.nlog
2..C.log
2..D.n—
1.下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关6的是..o直接插入排序和快速排.快速排序和归并排序A.・B.直接选择排序和归并排..直接插入排序和归并排序C.・D.一组记录的排序码为则利用堆排序的方法建立的初始堆为746,79,56,38,40,84,・・A.79,46,56,38,40,
8..B.84,79,56,38,40,46C.84,79,56,46,40,
3..D.84,56,79,40,46,
38.一组记录的排序码为则利用快速排序的方法，以第一个记录为846,79,56,38,40,84,基准得到的一次划分结果为.・A.38,4,46,56,79,
8..B.40,38,46,79,56,84C.40,38,46,56,79,
8..D.40,38,46,84,56,
79.用某种排序方法对线性表进行排序时，元素序列的
9.25,84,21,47,15,27,68,35,20变化情况如下125,84,21,47,15,27,68,35,20220,15,21,25,47,27,68,35,84315,20,21,25,35,27,47,68,84415,20,21,25,27,35,47,68,84则所采用的排序方法是选择排..希尔排.归并排..快速排序A.B.・C.D..快速排序方法在•.情况下最不利于发挥其长处10要排序的数据量太…..要排序的数据中含有多个相同值A.B要排序的数据已基本有一要排序的数据个数为奇数C.D.。
个人认证
优秀文档
获得点赞 0
