数据结构考题

一、选择题（12525分）1下面关于算法说法错误的是。BA算法最终必须由计算机程序实现B为解决某问题的算法同为该问题编写的程序含义是相同的C算法的可行性是指指令不能有二义性D以上几个都是错误的2在下面的程序段中，对X的赋值语句的频度为。CFORI1TONDOFORJ1TONDOXX1AO2NBONCON2DOLOG2N3下述哪一条是顺序存储结构的优点。AA存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构的存储表示4链表不具有的特点是。BA插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比5对于一个头指针为HEAD的带头结点的单链表，判定该表为空表的条件是。BAHEADNULLBHEADNEXTNULLCHEADNEXTHEADDHEADNULL6对于栈操作数据的原则是。BA先进先出B后进先出C后进后出D不分顺序7一个栈的输入序列为123N，若输出序列的第一个元素是N，输出第I（1,G的拓扑序列是。AAV1,V3,V4,V6,V2,V5,V7BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7DV1,V2,V5,V3,V4,V6,V722适用于折半查找的表的存储方式及元素排列要求为。DA链接方式存储，元素无序B链接方式存储，元素有序C顺序方式存储，元素无序D顺序方式存储，元素有序23当采用分快查找时，数据的组织方式为。BA数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D数据分成若干块，每块（除最后一块外）中数据个数需相同24假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行多少次探测。DAK1次BK次CK1次DK（K1）/2次25下列四个序列中，哪一个是堆。CA75,65,30,15,25,45,20,10B75,65,45,10,30,25,20,15C75,45,65,30,15,25,20,10D75,45,65,10,25,30,20,15二、填空题（21020分）1在一个长度为N的顺序表中第I个元素（1NEXTNULLPALANEXTPBLBNEXT/初始化/归并DELETELADELETELB/释放LA和LB的头结点/UNION2试写出直接插入排序的算法。2020学年第学期数据结构课程试卷标准答案及评分标准A/B卷专业班级注意标题请用宋体4号，内容请用宋体5号。五、选择题（12525分）15BCABB610BBCCB1115BBCAB1620AABCD2125ADBDC六、填空题（21020分）1NI12312334XYXYXYWWY52326697HIDJKEBLFGCA8第K列非零元素个数9910散列HASH查找七、简答题（78101035分）1（行、列、元素个数及每行各1分）44410222103322142352树和二叉树的区别有三一是二叉树的度至多为2，树无此限制；（2分）二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；（2分）三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。（2分）树和二叉树逻辑上都是树形结构，二叉树不是树的特例。（2分）3设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列1ABGFDEC2EACFBDG34顶点ABCDEFGHWVEI016342413392252VLI02924373113392252（4分）活动A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15A16A17EI000016633424131313392222LI281803292431343731203613392240（4分）关键路径是活动与顶点的对照表A1A2A3A4A5A6223ADADF132GAFD1323BGFDA1234DFACGBE1234DFACGB133CFHGW，长52。A7A8A9A10A11A12A13A14A15A16A17（2分）八、算法实现题（21020分）1/LA和LB均不空1GETELEMLA,I,AIGETELEMLB,J,BJIFAI,将此树转化为二叉树后，B的兄弟为（）。AABCCIDB19设有1000个无序的元素，希望用最快的速度挑选出其中前10个最小的元素，最好选用（）排序法。A冒泡排序B快速排序C堆排序D基数排序20散列法存储的基本思想是根据关键码值来决定存储地址，碰撞（冲突）指的是（）。A两个元素具有相同序号B两个元素的关键码值不同，而非码属性相同C不同关键码值对应到相同的存储地址D负载因子过大21由两个栈共享一个向量空间的好处是（）A减少存取时间，降低下溢发生的机率B节省存储空间，降低上溢发生的机率C减少存取时间，降低上溢发生的机率D节省存储空间，降低下溢发生的机率22在一个链队列中,假定FRONT和REAR分别为队首和队尾指针，则指针S所指的结点入队的操作为AFRONTNEXTSBSNEXTREARREARSCREARNEXTSREARSDSNEXTFRONTFRONTS23某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二叉树。A空或只有一个结点B高度等于其结点数C任意结点无左孩子D任意结点无右孩子24用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）A选择排序B希尔排序C归并排序D快速排序25设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。A25B10C7D126下列哪一个关键字序列不符合堆的定义（）AA、C、D、G、H、M、P、Q、R、XBA、C、M、D、H、P、X、G、Q、RCA、D、P、R、C、Q、X、M、H、GDA、D、C、M、P、G、H、X、R、Q27图的深度优先遍历类似于二叉树的（）。A先序遍历B中序遍历C后序遍历D层次遍历28下列二叉排序树中，满足平衡二叉树定义的是（）。29若要设计一个判别表达式中左、右括号是否配对的算法，采用数据结构最佳。A顺序表B栈C队列D单链表30对基本有序的N个记录的表作快速排序算法的时间复杂度是（）。AONBON2CONLOGNDON3二、判断题（11010分）1算法的时间复杂度是问题规模的函数，与输入的初始状态无关。（）2链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。3折半查找只适合用于有序表，包括有序的顺序表和有序的链表。（）4栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）5在有N个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要N1条弧。（）6在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（）7对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。8在N个结点的无向图中，若边数大于N1,则该图必是连通图。（）9在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（）10一棵有N个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为I的结点的左儿子的编号为2I2INEXTPBHBNEXTLCPCHA；/初始化（1分）WHILEPAPCPAPAPANEXT（2分）ELSEPCNEXTPBPCPBPBPBNEXT（2分）PCNEXTPAPAPB/插入剩余段（1分）FREEHB/释放LB的头结点/MERGELIST_L2二叉链表存储的二叉树的层次遍历的算法（共8分）VOIDBFSTRAVERSEBITREETINITQUEUEQ/置空的辅助队列QIFTENQUEUEQ,T/根结点入队列（1分）WHILEQUEUEEMPTYQ（1分）DEQUEUEQ,P/队头元素出队并置为P（1分）VISITP（1分）IFPLCHILDENQUEUEQ,PLCHILD/左子树根入队列（2分）IFPRCHILDENQUEUEQ,PRCHILD/右子树根入队列（2分）/WHILE单项选择题（13030分）1数据结构在计算机内存中的表示是指（）。A数据的存储结构B数据结构C数据的逻辑结构D数据元素之间的关系2算法是指对特定问题求解步骤的一种描述，它是指令的有限序列。它必须具备和输入、输出等五个特性。A确定性、有穷性、稳定性B可执行性、正确性、安全性C可行性、确定性、有穷性D易读性、易改性、正确性3以下与数据的存储结构无关的术语是（）。A循环队列B链表C哈希表D栈4若线性表最常用的运算是存取第I个元素及其前驱的值，则采用（）存储方式节省时间。A单链表B双链表C单循环链表D顺序表5在单链表中，在P所指结点之后插入S所指结点的操作是（）。ASNEXTPNEXTPNEXTSBSNEXTPPNEXTSCPNEXTSSNEXTPDPNEXTSNEXTSNEXTP6若频繁地对线性表进行插入和删除操作，该线性表应该采用存储结构。A散列B顺序C链式D索引7一个栈的的进栈序列是A,B,C,D,E,则栈的输出序列不可能是（）。AEDCBABDECBACDCEABDABCDE8判定一个循环队列QU最多元素个数为M0为满的条件是（）。AQUFRONT（QUREAR1）M0BQUFRONT（QUREAR1）M0CQUFRONTQUREARDQUFRONTQUREAR9线性表的顺序存储结构是一种（）的存储结构。A随机存取B顺序存取C索引存取D散列存取10一个向量第一个元素的存储地址是100，每个元素占2个存储空间，则第五个元素的地址是。A110B108C100D12011下面关于串的的叙述中，哪一个是不正确的（）A串是字符的有限序列B空串是由空格构成的串C模式匹配是串的一种重要运算D串既可以采用顺序存储，也可以采用链式存储12广义表GETHEADGETTAILGETHEADA,B,C,D操作的结果为（）ABBBCDDD13已知某二叉树的后序遍历序列是DABEC,中序遍历序列是DEBAC，它的前序遍历序列是（）。AACBEDBDECABCDEABCDCEDBA14下面哪一方法可以判断出一个有向图是否有环（回路）（）。A深度优先遍历B拓扑排序C求最短路径D求关键路径15深度为5的二叉树至多有_个结点A16B32C31D1016栈和队列的相同之处是（）。A元素的进出满足先进后出B元素的进出满足后进先出C只允许在端点进行插入和删除操作D无共同点17如果一颗哈夫曼树T有N0个叶子结点，那么树T共有（）个结点。A2N01B2N01C3N01D3N0118已知一棵树边的集合为,将此树转化为二叉树后，B的兄弟为（）AABCCIDB19在一个具有N个顶点的无向图中，要连通全部顶点至少需要条边。ANBN1CN1DN边数20散列法存储的基本思想是根据关键码值来决定存储地址，碰撞（冲突）指的是（）。20散列法存储的基本思想是根据关键码值来决定存储地址，碰撞（冲突）指的是（）。A两个元素具有相同序号B两个元素的关键码值不同，而非码属性相同C不同关键码值对应到相同的存储地址D负载因子过大21在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而多的是（）。A快速排序B希尔排序C冒泡排序D堆排序22在一个链队列中,假定FRONT和REAR分别为队首和队尾指针，则插入指针S所指的结点的操作为。AFRONTNEXTSBSNEXTREARREARSCREARNEXTSREARSDSNEXTFRONTFRONTS23某二叉树的前序序列和后序序列正好相反，则该二叉树一定是的二叉树。A空或只有一个结点。B高度等于其结点数。C任一结点无左孩子。D任一结点无右孩子。24对N个结点的线性表进行排序，平均情况下归并排序的时间复杂性为。AONNBONLOG2NCONDOLOG2N25设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。A25B10C7D126一组记录的输入顺序为46,79,56,38,40,84，则利用堆排序方法建立的初始堆为。A79,46,56,38,40,80B38,40,56,79,46,84C84,79,56,38,40,46D84,56,79,40,46,3827图的深度优先遍历类似于二叉树的（）。A先序遍历B中序遍历C后序遍历D层次遍历28下列二叉排序树中，满足平衡二叉树定义的是（）。29以下哪一个不是栈的基本运算A从栈顶插入一个新元素B从栈底删除一个元素C判断一个栈是否为空D读取栈顶元素的值30若A1，B2，C3，D4，则后缀式DB/CCAB的运算结果为（）。A18B16C15D17二、判断题（11010分）1算法的时间复杂度是问题规模的函数，与输入的初始状态无关。（）2两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）3单链表从任何一个结点出发，都能访问到所有结点。（）4一棵二叉树中叶子结点的个数等于度为2的结点个数加1。（）5折半插入排序所需比较次数与待排序记录的初始排列状态相关。（）6在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（）7对一棵二叉排序树按中序方法遍历得出的结点序列是从小到大的序列。8若将一棵树转换成二叉树，则该二叉树的根结点一定没有右子树（）。9对于任一个图，从某顶点出发进行一次深度或广度优先搜索,可以访问图中每一个顶点（）。10一棵有N个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为I的结点的左儿子的编号为2I2INEXTPBBNEXTCPCMALLOCSIZEOFLNODEPCNEXTNULLWHILEPAELSEIFPADATAPBDATAPBPBNEXTELSESMALLOCSIZEOFLNODESDATAPADATASNEXTNULLPCNEXTSPCSPAPANEXTPBPBNEXT单项选择题每小题1分，共15分1从逻辑上可以把数据结构分为（）两大类。A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D初等结构、构造型结构2以下数据结构中，（）是非线性数据结构A树B字符串C队D栈3线性表是具有N个（）的有限序列（N0）。A表元素B字符C数据元素D数据项E信息项4链表不具有的特点是（）A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比205设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构B队列C线性表的链式存储结构D栈6栈和队都是（）A顺序存储的线性结构B链式存储的非线性结构C限制存取点的线性结构D限制存取点的非线性结构7串的长度是指（）A串中所含不同字母的个数B串中所含字符的个数C串中所含不同字符的个数D串中所含非空格字符的个数8对稀疏矩阵进行压缩存储目的是（）。A便于进行矩阵运算B便于输入和输出C节省存储空间D降低运算的时间复杂度9一个N个顶点的连通无向图，其边的个数至少为（）。AN1BNCN1DNLOGN；10下面哪一方法可以判断出一个有向图是否有环（回路）A深度优先遍历B拓扑排序C求最短路径D求关键路径11用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A栈B队列C树D图12在下列存储形式中，哪一个不是树的存储形式。A双亲表示法B孩子链表表示法C孩子兄弟表示法D顺序存储表示法13对线性表进行二分查找时，要求线性表必须。A以顺序方式存储B以顺序方式存储,且数据元素有序C以链接方式存储D以链接方式存储,且数据元素有序14直接插入排序在最好情况下的时间复杂度为（）。AOLOGNBONCONLOGNDON215链表适用于（）查找。A顺序B二分法C顺序，也能二分法D随机填空题（每空2分，共20分）1数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度、2最大容量为N的循环队列，队尾指针是REAR，队头是FR