《数据结构试题,模拟考试题(可编辑).doc》由会员分享，可在线阅读，更多相关《数据结构试题,模拟考试题(可编辑).doc（38页珍藏版）》请在三一办公上搜索。
1、数据结构试题,模拟考试题 数据结构试题单选题 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构2采用线性链表表示一个向量时要求占用的存储空间地址D A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续3采用顺序搜索方法查找长度为n的顺序表时搜索成功的平均搜索长度为 D A n B n2 C n-1 2 D n1 24在一个单链表中若q结点是p结点的前驱结点若在q与p之间插入结点s则执行 D A slink plink plink s B plink s slink qC plink slink slink p D qlink s slin
2、k p5如果想在4092个数据中只需要选择其中最小的5个采用 C 方法最好 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6设有两个串t和p求p在t中首次出现的位置的运算叫做 B A 求子串 B 模式匹配 C 串替换 D 串连接7在数组A中每一个数组元素Aij占用3个存储字行下标i从1到8列下标j从1到10所有数组元素相继存放于一个连续的存储空间中则存放该数组至少需要的存储字数是 C A 80 B 100 C 240 D 2708将一个递归算法改为对应的非递归算法时通常需要使用 A A 栈 B 队列 C 循环队列 D 优先队列9一个队列的进队列顺序是1 2 3 4则出队列顺序为 C
3、10在循环队列中用数组A0m-1 存放队列元素其队头和队尾指针分别为front和rear则当前队列中的元素个数是 D A front - rear 1 m B rear - front 1 mC front - rear m m D rear - front m m11一个数组元素ai与 A 的表示等价A ai B ai C ai D ai 12若需要利用形参直接访问实参则应把形参变量说明为 B 参数A 指针 B 引用 C 值 D 变量13下面程序段的时间复杂度为 C for int i 0i mi for int j 0j nj aij ijA O m2 B O n2 C O mn D O
4、mn 14下面程序段的时间复杂度为 B int f unsigned int n if n 0 n 1 return 1 else return nf n-1 A O 1 B O n C O n2 D O n 15线性表若是采用链式存储结构时要求内存中可用存储单元的地址 D A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续或不连续都可以16数据结构的定义为 DS 其中D是 B 的集合A 算法 B数据元素 C 数据操作 D 逻辑结构17算法分析的目的是 A A 找出数据结构的合理性B 研究算法中输入和输出的关系C 分析算法的效率以求改进D 分析算法的易懂性和文档性18在一个单链
5、表中若p所指结点不是最后结点在p之后插入s所指结点则执行 B A s- link pp- link sB s- link p- linkp- link sC s- link p- linkp sD p- link ss- link p19设单链表中结点结构为 datalink 已知指针q所指结点是指针p所指结点的直接前驱若在q与p之间插入结点s则应执行下列哪一个操作 B A s- link p- link p- link s B q- link s s- link pC p- link s- links- link p D p- link s s- link q20设单链表中结点结构为 dat
6、alink 若想摘除结点p的直接后继则应执行下列哪一个操作 A A p- link p- link- link B p p- link p- link p- link- linkC p- link p- link D p p- link- link21设单循环链表中结点的结构为datalink且rear是指向非空的带表头结点的单循环链表的尾结点的指针若想删除链表第一个结点则应执行下列哪一个操作 D A s rear rear rear- link delete s B rear rear- link delete rear C rear rear- link- link delete rear
7、 D s rear- link- link rear- link- link s- link delete s22设单循环链表中结点的结构为datalink且first为指向链表表头的指针current为链表当前指针在循环链表中检测current是否达到链表表尾的语句是 D A current- link null B first- link currentC first current D current- link first23一个栈的入栈序列为abc则出栈序列不可能的是 C A cba B bac C cab D acb24栈的数组表示中top为栈顶指针栈空的条件是 A A top 0
8、 B top Size C top Size D top -125栈和队列的共同特点是 C A 都是先进后出 B 都是先进先出C 只允许在端点处插入和删除 D 没有共同点26假定一个顺序存储的循环队列的队头和队尾指针分别为f和r 则判断队空的条件为 D A f1 r B r1 f C f 0 D f r27当利用大小为n 的数组顺序存储一个队列时该队列的最大长度为 B A n-2 B n-1 C n D n128当利用大小为n 的数组顺序存储一个栈时假定用top n 表示栈空则向这个栈插入一个元素时首先应执行 语句修改top指针A top B top- C top 0 D top29设链式栈中
9、结点的结构为data link且top是指向栈顶的指针若想摘除链式栈的栈顶结点并将被摘除结点的值保存到x中则应执行下列 A 操作A x top- data top top- link B top top- link x top- data C x top top top- link D x top- data30设循环队列的结构是 const int size 100 typedef int Data Type typedef struct Data Type datasize Int front rear Queue若有一个Queue类型的队列Q试问判断队列满的条件应是下列哪一个语句 D A
10、 Qfront Qrear B Qfront - Qrear size C Qfront Qrear size D Qfront Qrear1 size31设有一个递归算法如下int fact int n if n 0 return 1else return nfact n-1 下面正确的叙述是 B A 计算fact n 需要执行n次递归 B fact 7 5040 C 此递归算法最多只能计算到fact 8 D 以上结论都不对32设有一个递归算法如下int x int n if n 3 return 1else return x n-2 x n-4 1 试问计算 x x 8 时需要计算 D 次
11、x函数A 8 次 B 9次 C 16次 D 18次33设有广义表D abD 其长度为 B 深度为 A A B 3 C 2 D 534广义表A a 则表尾为 C A a B C 空表 D a35下列广义表是线性表的有 C A Ea bc B E aE C E ab D E aL 36递归表再入表纯表线性表之间的关系为 C A 再入表 递归表 纯表 线性表 B 递归表 线性表 再入表 纯表 C 递归表 再入表 纯表 线性表 D递归表 再入表 线性表 纯表37某二叉树的前序和后序序列正好相反则该二叉树一定是B的二叉树A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩
12、子38对于任何一棵二叉树T如果其终端结点数为n0度为2的结点为n2则 A A n0 n21 B n2 n01 C n0 2n21 D n2 2n01 39 由权值分别为118625的叶子结点生成一棵哈夫曼树它的带权路径长度为A 24 B 73 C 48 D 5340已知一个顺序存储的线性表设每个结点需占m个存储单元若第一个结点的地址为da1则第I 个结点的地址为AA da1 I-1 m B da1Im C da1-Im D da1 I1 m4134 具有35个结点的完全二叉树的深度为 A A 5 B 6 C 7 D 842对线性表进行折半搜索时要求线性表必须 C A 以链接方式存储且结点按关键
13、码有序排列 B 以数组方式存储 C 以数组方式存储且结点按关键码有序排列 D以链接方式存储43顺序搜索算法适合于存储结构为 B 的线性表A 散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储44采用折半搜索算法搜索长度为n的有序表时元素的平均搜索长度为 C A On2 B On log2n C Olog2n D On45对于一个具有n个顶点和e条边的无向图进行拓扑排序时总的时间为 A A n B n1 C n-1 D ne46判断一个有向图是否存在回路除了可以利用拓扑排序方法外还可以利用C A 求关键路径的方法 B 求最短路径的Dijkstra方法 C 深度优先遍历算法 D 广度优先
14、遍历算法47在10阶B-树中根结点所包含的关键码个数最多为C 最少为 A A 1 B 2 C 9 D 1048对包含n 个元素的散列表进行搜索平均搜索长度为 C A Olog2n B OnC 不直接依赖于n D 上述都不对填空题1数据的逻辑结构被分为集合结构线性结构树形结构图形结构 四种2数据的存储结构被分为顺序结构链接结构索引结构散列结构 四种3一种抽象数据类型包括数据 和操作 两个部分设有两个串p和q求p在q中首次出现的位置的运算称为模式匹配 栈队列逻辑上都是线性存储结构线性结构反映结点间的逻辑关系是一对一的图中的数据元素之间的关系是多对多的树形结构中数据元素间的关系是一对多的栈中存取数据
15、的原则后进先出队列中存取数据的原则先进先出8abccdcdccbaa模式P cdcc则第6次匹配成功10i 1为 i-1 2 1617已知具有n个元素的一维数组采用顺序存储结构每个元素占k个存储单元第一个元素的地址为LOC a1 那么LOC ai LOC a1 18在霍夫曼编码中若编码长度只允许小于等于4则除掉已对两个字符编码为0和10外还可以最多对 4 个字符编码19设高度为h的空二叉树的高度为-1只有一个结点的二叉树的高度为0若设二叉树只有度为2上度为0的结点则该二叉树中所含结点 21以折半搜索方法搜索一个线性表时此线性表必须是顺序存储的有序表22已知完全二叉树的第8层有8个结点则其叶子结
16、点数是68若完全二叉树的第7有10个叶子结点则整个二叉树的结点数最多是23523对于折半搜索所对应的判定树它既是一棵二叉搜索树又是一棵理想平衡树24假定对长度n 50的有序表进行折半搜索则对应的判定树高度为判定树中前层的结点数为最后一层的结点数为25在一个无向图中所有顶点的度数之和等于所有边数的倍在一个具有n个顶点的无向完全图中包含有 n n-1 2 条边在一个具有n个顶点的有向完全图中包含有 n n-1 条边26对于一个具有n个顶点和e条边的连通图其生成树中的顶点数和边数分别为n和n-127设线性表中元素的类型是实型其首地址为1024则线性表中第6个元素的存储位置是 1044 28在插入和选
17、择排序中若初始数据基本正序则选择插入排序若初始数据基本反序则最好选择选择排序29算法是对特定问题的求解步骤的一种描述它是指令的有限序列每一条指令表示一个或多个操作30对于一个具有n个顶点肯e 条边的无向图进行拓朴排序时总的进间为n31构造哈希函数有三种方法分别为 平方取中 法 除留余数 法 折迭移位 法32处理冲突的三种方法分别为 线性探测 随机探测 链地址法33对于含有n个顶点和e条边的无向连通图利用普里姆算法产生的最小生成树其时间复杂度为 n2 利用克鲁斯卡尔算法产生的最小生成树其时间复杂度为elog2e 34快速排序在平均情况下的时间复杂度为nlog2n在最坏情况下的时间复杂度为n2快速
18、排序在平均情况下的空间复杂度为log2n在最坏情况下的空间复杂度为n35假定一组记录的排序码为对其进行归并排序的过程中第二趟排序后的结果是36假定一组记录的排序码为对其进行快速排序的第一次划分的结果是37一个结点的子树的 个数 称为该结点的度度为 零 的结点称为叶结点或终端结点度不为 零 的结点称为分支结点或非终端结点树中各结点度的 最大值 称为树的度38设Ki Kj 1 i n 1 j nj i 且在排序前的序列中Ri领先于Rj i j 若排序后的序列中Ri仍领先于Rj则这种排序方法是稳定的反之是不稳定的40 在堆排序的过程中对任一分支结点进行调整运算的时间复杂度为log2n整个排序过程的时
19、间复杂度为nlog2n41在索引表中每个索引项至少包含有关键码值域和子表地址域这两项42假定一个线性表为abcdbaabdbcefcfgahijbkwteccdtaayb若按照字符串的第一个字母进行划分使得同一个字母被划分在一个子表中则得到的abc三个子表的长度分别为43对于包含个关键码的阶B-树其最小高度为最大高度为44从一棵B-树删除关键码的过程若最终引起树根结点的合并则新树比原树的高度减45假定要对长度n 100的线性表进行散列存储并采用开散列法处理冲突则对于长度m 20的散列表每个散列地址的同义词子表的长度平均为46在散列存储中装载因子又称为装载系数若用m表示散列表的长度n表示待散列存
20、储的元素的个数则等于nm47在有向图的邻接矩阵中第i行中1的个数是第i个顶点的出度第i列中1的个数是第i个顶点的入度在无向图的邻接矩阵中第i行列中1的个数是第i个顶点的度矩阵中1的个数的一半是图中的边数48在对m阶B-树中每个非根结点的关键码数最少为m2-1个最多为m-1个其子树棵数最少为m2最多为m判断题数据元素是数据的最小单位数据的逻辑结构是指各数据元素之间的逻辑关系是用户按使用需要建立的 数据结构是指相互之间存在一种或多种关系的数据元素的全体从逻辑关系上讲数据结构主要分为两大类线性结构和非线性结构线性表的逻辑顺序与物理顺序总是一致的二维数组是其数组元素为线性表的线性表每种数据结构都应具备
21、三种基本运算插入删除搜索非空线性表中任意一个数据元素都有且仅有一个直接前驱元素 空串与由空格组成的串没有区别 将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配深度为h的非空二叉树的第层最多有2h-1个结点 完全二叉树就是满二叉树已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树 带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点则它一定是该子树的前序遍历结果序列的最后一个结点17任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间18最优二叉搜索树一定是平衡的二叉搜
22、索树19AOE网是一种带权的无环连通图 22线性表中所有结点的类型必须相同n个结点的有向图若它有n n1 条边则它一定是强连通的任何无环的有向图其结点都可以排在一个拓扑序列里 27用邻接矩阵存储一个图时在不考虑压缩存储的情况下所占用的存储空间大小只与图中顶点个数有关而与图的边数无关28邻接表只能用于有向图的存储邻接矩阵对于有向图和无向图的存储都适用29连通分量是无向图中的极小连通子图30在网络中一定只有一条关键路径31关键活动不按期完成就会影响整个工程的完成时间32平衡二叉树的左右子树深度之差的绝对值不超过1 33快速排序是对起泡排序的一种改进 34直接选择排序稳定35堆排序占用的辅助空间很大
23、36在散列法中采取开散列法来解决冲突时其装载因子的取值一定在之间37B-树是一种动态索引结构它既适用于随机搜索也适用于顺序搜索38在散列法中一个可用散列函数必须保证绝对不产生冲突39任何一个关键活动延迟那么整个工程将会延迟40任何一个关键活动提前完成那么整个工程将会提前完成四运算应用题 1在一个有n个元素的顺序表的第i个元素1 i n之前插入一个新元素时需要向后移动多少个元素答案需要向后移动 n- i 1个元素当一个栈的进栈序列为1234567时可能的出栈序列有多少种6457321是否是合理的出栈序列答案 可能的出栈序列有 种6457321不是合理的出栈序列简单直接选择排序是一种稳定的排序方法
24、吗试举例说明答案是不稳定的排序方法下面就是不稳定的例子只要能举出反例即可 275 275 512 061 i 1 061 275 512 275 i 2 061 275 512 275 i 3 061 275 275 512 4 20 30 40 50 60 70 采用折半搜索时搜索成功的平均搜索长度是多少答案 ASLsucc 11 22 34 7 17 75 在结点个数为n n 1 的各棵树中高度最小的树的高度是多少它有多少个叶结点多少个分支结点高度最大的树的高度是多少它有多少个叶结点多少个分支结点答案结点个数为n时高度最小的树的高度为1有2层它有n-1个叶结点1个分支结点高度最大的树的高度
25、为n-1有n层它有1个叶结点n-1个分支结点6 一棵高度为h的满k叉树有如下性质 第h层上的结点都是叶结点 其余各层上每个结点都有k棵非空子树 如果按层次自顶向下 同一层自左向右 顺序从1开始对全部结点进行编号 试问 1 各层的结点个数是多少 2 编号为i的结点的父结点 若存在 的编号是多少 3 编号为i的结点的第m个孩子结点 若存在 的编号是多少 4 编号为i的结点有右兄弟的条件是什么 其右兄弟结点的编号是多少 5 若结点个数为 n 则高度h是n 的什么函数关系答案1各层的结点个数是ki i 012h 2编号为i的结点的父结点 若存在 的编号是 ik-2 k3编号为i的结点的第m个孩子结点
26、若存在 的编号是 i-1 km14当 i-1 k 0时有右兄弟 右兄弟的编号为 i15若结点个数为 n 则高度h和n 的关系为h logk n k-1 1 -1 n 0时h -1 7 1 A - B C 2 A B D E F A D C 3 A B E F 注按C的优先级 4 A B C C D C E 答案各中缀表达式的后缀形式如下 1AB-C 2 ABDEFADC 3 ABEF 4 ABC CE 8 1 D A c B e C a L b c d 2 J1 J2 J1 a J3 J1 J3 J1 答案广义表1的图形表示为广义表2的图形表示为广义表1的存储表示为广义表2的存储表示为9题目1
27、1将下面的森林变换成二叉树7分答案10将算术表达式 ab c de f gh 转化为二叉树答案11答案其中的一个拓扑序列为V1V2V3V4V5V6V7 12 将给定的图简化为最小的生成树要求从顶点1出发7分答案 13某子系统在通信联络中只可能出现8种字符其出现的概率分别为005029007008014023003011试设计赫夫曼编码答案为方便起见设各种字符的权值w 529781423311 因为n 8所以要构造的赫夫曼树共有m 2n-1 28-1 15个结点生成的赫夫曼树为下图所示赫夫曼编码为概率为023的字符编码为00概率为011的字符编码为010概率为005的字符编码为0110概率为00
28、3的字符编码为0111概率为029的字符编码为10 概率为014的字符编码为110 概率为007的字符编码为1110 概率为008的字符编码为111114已知一棵二叉树的前序遍历的结果是ABECDFGHIJ 中序遍历的结果是EBCDAFHIGJ 试画出这棵二叉树并给出这棵二叉树的后序遍历序列答案根据前序序列和中序序列能得到唯一的二叉树所得二叉树如图这棵二叉树的后序遍历序列为EDCBIHJGFA15在结点个数为n n 1 的各棵树中高度最小的树的高度是多少它有多少个叶结点多少个分支结点高度最大的树的高度是多少它有多少个叶结点多少个分支结点答案结点个数为n时高度最小的树的高度为1有2层它有n-1个
29、叶结点1个分支结点高度最大的树的高度为n-1有n层它有1个叶结点n-1个分支结点16 对于一个高度为h的AVL树其最少结点数是多少反之对于一个有n个结点的AVL树 其最大高度是多少 最小高度是多少答案设高度为h 空树的高度为-1 的AVL树的最少结点为Nh则Nh Fh3 -1Fh 是斐波那契数又设AVL树有n个结点则其最大高度不超过32log2 n1 最小高度为log2 n1 -1177-7 设有序顺序表中的元素依次为017 094 154 170 275503 509 512 553 612 677 765 897 908试画出对其进行折半搜索时的判定树 并计算搜索成功的平均搜索长度和搜索不
30、成功的平均搜索长度答案折半搜索时的判定树为ASLSUCC 1141223447 4514ASLUNSUCC 11531414 591518试对下图所示的AOE网络 1 这个工程最早可能在什么时间结束 2 求每个事件的最早开始时间Vei和最迟开始时间Vli 3 求每个活动的最早开始时间e 和最迟开始时间l 4 确定哪些活动是关键活动画出由所有关键活动构成的图指出哪些活动加速可使整个工程提前完成答案按拓朴有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l根据l-e是否等于0来确定关键活动从而确定关键路径Ve019152938
31、43Vl01915373843 12 13 32 24 25 35 46 56 e00151919152938L170152719273738l-e1700801280此工程最早完成时间为43关键路径为 13 32 25 56 19已知有五个待排序的记录其关键字分别为256301751129937863742694076438请用快速排序的方法将它们从小到大排列答案第一次排序076129256751937863742694301439第二次排序076129256438301694742751863937第三次排序076129256301438694742751863937第四次排序076129
32、256301438694742751863937第五次排序07612925630143869474275186393720设有150个记录要存储到散列表中 并利用线性探查法解决冲突 要求找到所需记录的平均比较次数不超过2次试问散列表需要设计多大 设 是散列表的装载因子则有ASLsucc 11 1- 2 答案已知要存储的记录数为n 150查找成功的平均查找长度为ASLsucc 2则有ASLsucc 12111- 2 解得 23 又有 nm 150m两式联立得150m23解得m225所以散列表需要设计225个单位五算法分析题1给出下列递归过程的执行结果 void unknown int w if
33、w unknown w-1 for int i 1 i w i cout w cout endl 调用语句为 unknown 4 答案 1 1 2 23 3 3 4 4 4 4 2给出递归过程的执行结果 void unknown int n cout n 10 if int n 10 unknown int n 10 调用语句为unknown 582 答案 2853给出递归过程的执行结果int unknown int m int value if m value 3 else value unknown m-1 5 return value 执行语句为 cout unknown 3 答案 18
34、 4 Amn假设A00存放位置在64410A22存放位置在67610A33101010进制表示答案设数组元素Aij存放在起始地址为Loc ij 的存储单元中 因为Loc 22 Loc 00 2n2 6442n2 676 所以n 676-2-644 2 15 所以Loc 33 Loc 00 3153 644453 6925设单链表结构为 struct ListNode int data ListNode link 下面的程序是以单链表为存储结构 实现二路归并排序的算法 要求链表不另外占用存储空间 排序过程中不移动结点中的元素 只改各链结点中的指针 排序后r仍指示结果链表的第一个结点在初始状态下
35、所有待排序记录链接在一个以r为头指针的单链表中例如在算法实现时利用了一个队列做为辅助存储 存储各有序链表构成的归并段的链头指针初始时 各初始归并段为只有一个结点的有序链表队列的数据类型为Queue 其可直接使用的相关操作有 置空队列操作makeEmpty 将指针x加入到队列的队尾操作EnQueue ListNode x 退出队头元素 其值由函数返回的操作ListNode DlQueue 判队列空否的函数 空则返回1 不空则返回0int IsEmpty 解决方法提示 程序首先对待排序的单链表进行一次扫描 将它划分为若干有序的子链表 其表头 指针存放在一个指针队列中 当队列不空时 从队列中退出两个
36、有序子链表 对它们进行二路归并 结果链表的表头指针存放到队列中 如果队列中退出一个有序子链表后变成空队列 则算法结束这个有序子链表即为所求在算法实现时有 6 处语句缺失请阅读程序后补上 1 两路归并算法void merge ListNode ha ListNode hb ListNode hc ListNode pa pb pc if hadata hbdata hc ha pa halink pb hb else hc hb pb hblink pa ha pc hc while pa pb if padata pbdata pclink pa pc pa pa palink else pc
37、link pb pc pb pb pblink if pa pclink pa else pclink pb 2 归并排序主程序void mergesort ListNode r ListNode s t Queue Q if r returns r QEnQueue r while s t slink while t 0 sdata tdata s t t tlink if t slink 0 s t QEnQueue s while QIsEmpty r QDlQueue if QIsEmpty break s QDlQueue merge r s t QEnQueue t 6请读下列程序该程序是在单链表中删除一个结点的算法为空出的地方填上正确的语句7分 void demo2 LinkList headListNode p head 是带头结点的单链表删除P指向的结点 ListNode q head while - next p q q- next if q Error p not in head q- next p- next free p 已知一完全二叉树从根结点开始自顶向下同一层自左向右连续编号根结点的编号为0阅读以下程序请回答该程序所实现的功能 template void
