《数据结构与算法》题：选择题、判断题

第一章绪论从逻辑上可以把数据结构分为（C ）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结在下面的程序段中，对x的赋值语句的频度为（C 。For（k=1；k<=n；k++）For（j=1；j<=n；j++）x=x＋1；A．O(2n) B．O(n) C．O(n2) D．O(log2n)采用顺序存储结构表示数据时，相邻的数据元素的存储地址（A 。B．一定不连续C．不一定连续 D．部分连续、部分不连续下面关于算法的说法，正确的是（D 。A．算法的时间复杂度一般与算法的空间复杂度成正比B．解决某问题的算法可能有多种，但肯定采用相同的数据结C．算法的可行性是指算法的指令不能有二义性D．同一个算法，实现语言的级别越高，执行效率就越低在发生非法操作时，算法能够作出适当处理的特性称为（B 。正确性 B．健壮性 C．可读性 D．可移植性第二章线性表线性表是（A 。一个有限序列，可以为空 B．一个有限序列，不能为C．一个无限序列，可以为空 D．一个无限序列，不能为对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的插入一个元素时平均要移动表中的（A ）个元素。．n/2 （n＋1）/2 C（n－1）/2 ．n线性表采用链式存储时，其地址（D 。A．必须是连续的B．部分地址必须是连续C．一定是不连续的D．连续与否均可以用链表表示线性表的优点是（C 。便于随机存取B．花费的存储空间较顺序存储少C．D链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则.采用（C）存储方式最节省运算时间。BCD．带头结点的双向循环链表下面关于线性表的叙述，错误的是（B 。A．线性表采用顺序存储，必须占用一片地址连续的单B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链式存储，不必占用一片地址连续的单元D．线性表采用链式存储，不便于进行插入和删除操作单链表中，增加一个头结点的目的是为了（C 。A．使单链表至少有一个结点 B．标识表结点中首结点的位置C．方便运算的实现 D．说明单链表是线性表的链式存在单链表指针为p的结点之后插入指针为s结点，正确的操作是（B 。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；在双向链表存储结构中，删除p所指的结点时须修改指针（A （p->prior->next=p->next;（p->next）>prior=->prior;B．p->prior=（p->prior）->prior;（p->prior）->next=p;C（p->next）->prior=p;->rlink（p->next）->next;D．p->next=（p->prior）->prior;p->prior=（p->next）->next完成在双向循环链表结点p之后插入s的操作是（D 。A．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;若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ B ）存储方式最节省运算时间。单链表 B．顺序表 C．双向链表 D．单循环链表则采用（D）存储方式最节省运算时间。B．仅有头指针的单循环链表CD第三章栈和队列向一个栈顶指针为top的链栈中插入一个p所指结点时，其操作步骤为（C ）。top->next=p； B．p->next=top->next；top->next=p；C．p->next=top；top=p； D．p->next=top；top=top->next；...对于栈操作数据的原则是（B ）A．先进先出B．后进先出C．后进后出D．不分顺序若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若pn是n，则Pi为（D 。A．i B．n－i C．n－i＋l D．不确定表达式a*（b－c）＋d的后缀表达式是（B ）A．abcd*－＋B．abc－*d＋C．abc*－d＋D．＋－*abcd采用顺序存储的两个栈的共享空间S[1..m]，用top[i]代表第i个栈的栈顶栈1的底在S[1]，栈2的底在S[m]，则栈满的条件是（B ）。A．top[2]－top[1]=0B．top[1]＋1=top[2]C．top[1]＋top[2]=mD．top[1]=top[2]一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（C ）。edcbaB．decbaC．dceabD．abcde在一个链队列中若r分别为队首队尾指针则插入p所指结点的操作（B 。A．f->next=p；f=pB．r->next=p；r=pC．p->next=r；r=pD．p->next=f；f=p用不带头结点的单链表存储队列时，在进行删除运算时（D ）。仅修改头指针B．仅修改尾指针CD递归过程或函数调用时，处理参数与返回地址，要用一种称为（C ）的数据结构。队列 B．静态链表 C．栈 D．顺序表栈和队都是（C 。顺序存储的线性结构B．链式存储的非线性结构C．D第四章字符串与线性结构的扩展下面关于串的叙述，错误的是（C 。A．串是字符的有限序列B．串既可以采用顺序存储，也可以采用链式存C．空串是由空格构成的串D．模式匹配是串的一种重要运算串的长度是指（B 。A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数3.M6（每个字符占一个存储单元，即一个字节）i08，j110，M至少需要（1（D）个M85（2（AMM[8][5]M按列优先方式存储时的（3（C）元素的起始地址一致。（1）A.90B.180C.240D.540（2）A.108B.114C.54D.60（3）A.M[8][5] B.M[3][10]C.M[5][8]D.M[0][9]A3i18，列下标j110，SA开始连续存放在存储器内，存放该数组至少需要的单元个数是1（C；若该数组按行存放，元素A[8][52（D；若该数组按列存放，元素A[8][53（B。（1）A.80B.100C.240D.270（2）A.SA+141B.SA+144C.SA+222D.SA+225（3）A.SA+141B.SA+180C.SA+117D.SA+225稀疏矩阵采用压缩存储，一般有（C）两种方法A．二维数组和三维数组 B．三元组和散列C．三元组表和十字链表 D．散列和十字链表第五章树结构下列说法正确的是（C。A．二叉树中任何一个结点的度都为2 B．二叉树的度为2C．一棵二叉树的度可小于2 D．任何一棵二叉树中至少有一个结点的度为2n（n＞0（C。A．2n－1 B．n－1 C．n＋l D．2n＋l线索化二叉树中，某结点*p（B。p->rtag=1C.p->ltag=1如果结点A有3个兄弟，而且B是A的双亲，则B的度是（BA．3 B．4D．1某二叉树TnTn，v，1，而vv1，这是按（B）编号的。中序遍历序列 B.先序遍历序列 C.后序遍历序列 D.层次顺序设F是一个森林是由F转换得到的二叉树中有n个非终端结点中右指域为空的结点有（C ）个。n－1B．nC．n＋l D．n＋2一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C 。A．500B．501C．490 D．495设森林F中有3棵树，第1、第2和第3棵树的结点个数分别为和N3。与林F对应的二叉树根结点的右子树上的结点个数是（D 。A．N1B．N1＋N2C．N2 D．N2＋N3任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（A 。不发生改变 B.发生改变 C.不能确定 D.以上都不对dabec，中序遍历序列为debac，则先序遍历序列为（ D 。cbed B.decab C.deabc D.cedba若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序历的结果为（D 。gcefhaB.gdbecfhaC.bdgaechfD.gdbehfca一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ B 。所有的结点均无左孩子 B.所有的结点均无右孩子C.只有一个叶子结点D.是一棵满二叉树设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结数至少为（B 。A.2hB.2h－1C.2h＋1D.h＋1一个具有567个结点的二叉树的高h为（D 。A.9 B.10 C.9～566之间 D.10～567之间第六章图结构n条边的无向图的邻接表的存储中，边结点的个数有（A 。nB.2nC.n/2D.n×nn条边的无向图的邻接多重表的存储中，边结点的个数有（A 。n B.2n C.n/2 D.n×n下列哪一种图的邻接矩阵是对称矩阵？（B ）有向图 B.无向图 C.AOV网 D.AOE网最短路径的生成算法可用（C 。普利姆算法 B.克鲁斯卡尔算法 C.迪杰斯特拉算法 D.哈夫曼算法一个无向图的邻接表如下图所示。vertexfirstedge0v013^1v1023^2v21^3v301^从顶点v0出发进行深度优先搜索，经历的结点顺序为（B 。A.v0，v3，v2，v1B.v0，v1，v2，v3C.v0，v2，v1，v3D.v0，v1，v3，v2从顶点v0出发进行广度优先搜索，经历的结点顺序为（D 。A.v0，v3，v2，v1B.v0，v1，v2，v3C.v0，v2，v1，v3D.v0，v1，v3，v2设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（D 。O(nlog2e)B.O(e×n)C.O(elog2n)D.O(n＋e)含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小生成树，其时间复度为（A 。O(elog2e)B.O(e×n)C.O(elog2n)D.O(nlog2n)关键路径是事件结点网络中（A 。B.从源点到汇点的最短路径C.最长的回路D.最短的回路下面关于求关键路径的说法，不正确的是（C 。求关键路径是以拓扑排序为基础的一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同持续时间的差关键活动一定位于关键路径上有10个结点的无向图至少有（B ）条边才能确保其是连通图。A.8B.9C.10D.11第七章查找静态查找表与动态查找表的根本区别在于（。B.施加在其上的操作不一样C.D.存储实现不一样在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（ A 。nB.1C.n+1D.n-1顺序查找适用于存储结构为（C ）的线性表。B.压缩存储C.D.索引存储用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为（C 。A．O(log2n2)B.O(nlog2n)C.O(n)D.O(log2n)适用于折半查找的表的存储方式与元素排列要求为（D 。方式存储，元素无序方式存储，元素有序顺序方式存储，元素无序顺序方式存储，元素有序有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率况下查找成功所需的平均比较次数为（B 。A.35/12B.37/12C.39/12D.43/127.在有序表上进行折半查找关键字为82的数据元素需要比较（C ）次。A.1B.2C.4D.514H（key）=key%114个结点：addr(84)=7如用二次探测再散列处理冲突则关键字为49的结点的地址是（D 。A.8B.3C.5D.9散列函数有一个共同的性质，即函数值应当以（D ）取其值域的每个值。最大概率 B.最小概率 C.平均概率 D.同等概率假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，少要进行（D ）次探测。k－1次 B.k次 C.k＋1次 D.k（k＋1）/2次在散列函数H（k）=k%m中，一般来讲，m应取（ C 。奇数 B.偶数 C.素数 D.充分大的数在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，查找成功的情况下，所探测到的这些位置上的键值（B 。B.一定不是同义词C.都相同D.不一定都是同义词第八章排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A 。B.C.D.归并排序设有1000个无序的元素希望用最快的速度挑选出其中前10个最大的元素最好用（C ）排序法。B.C.D.基数排序具有12个记录的序列，采用冒泡排序最少的比较次数是（C 。A.1 B.144 C.11 D.66下列四种排序方法中，要求内存容量最大的是（D 。B.C.D.归并排序初始序列已经按键值有序时用直接插入算法进行排序需要比较的次数（D 。n2B.nlog2nC.log2nD.n－1是（C。A.直接插入排序和快速排序B.快速排序和归并排序C.直接选择排序和归并排序D.直接插入排序和归并排序一组记录的排序码为（46，79，56，38，40，84，则利用堆排序的方法建立的初堆为（B 。A.79，46，56，38，40，84B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，38一组记录的排序码为（46，79，56，38，40，84，则利用快速排序的方法，以第个记录为基准得到的一次划分结果为（C 。A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，799.用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，