2024年大学试题(计算机科学)-数据结构考试近5年真题集锦（频考类试题）带答案

（图片大小可自由调整）2024年大学试题(计算机科学)-数据结构考试近5年真题集锦（频考类试题）带答案第I卷一.参考题库(共100题)1.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）2.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a.删除P结点的直接后继结点的语句序列是（）。 b.删除P结点的直接前驱结点的语句序列是（）。 c.删除P结点的语句序列是（）。 d.删除首元结点的语句序列是（）。 e.删除尾元结点的语句序列是（）。 （1）P=P->next； （2）P->next=P； （3）P->next=P->next->next； （4）P=P->next->next； （5）while（P!=NULL）P=P->next； （6）while（Q->next!=NULL）{P=Q；Q=Q->next；} （7）while（P->next!=Q）P=P->next； （8）while（P->next->next!=Q）P=P->next； （9）while（P->next->next!=NULL）P=P->next； （10）Q=P； （11）Q=P->next； （12）P=L； （13）L=L->next； （14）free（Q）；3.用5个权值{3，2，4，5，1}构造的哈夫曼（Huffman）树的带权路径长度是（）4.用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。5.待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后，结果序列为（）。6.中缀表达式3*（X+2）-5所对应的后缀表达式为（）。7.将如图所示的森林转换成二叉树。 8.堆是一个完全二叉树。9.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A、2B、3C、4D、610.设计顺序查找算法，将哨兵设在下标高端。11.对机器语言而言，存储结构是具体的。一般至在（）层次上讨论存储机构。12.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。13.在一个具有n个顶点的有向完全图中包含有（）条边A、n（n-1）/2B、n（n-1）C、n（n+1）/2D、n214.栈是实现过程和函数等子程序所必需的结构。15.数组就是矩阵，矩阵就是数组，这种说法（）A、正确B、错误C、前句对，后句错D、后句对16.对于一个图G，若边集E（G）为有向边的集合，则该图为（）。17.已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用（）。18.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为（）19.散列表的地址区间为0-17，散列函数为H（K）=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。存放元素59需要搜索的次数是（）。A、2B、3C、4D、520.当利用大小为N的数组存储循环队列时，该队列的最大长度是（）。A、N-2B、N-1C、ND、N+121.数据结构里，实参和形参的关系（）。A、实参传给形参B、实参的类型要与形参一致C、实参的个数要与实参一致D、实参的名称要与形参的一致22.数据的存储结构是逻辑结构用（）的实现。23.如果进栈的元素序列为A，B，C，D，则可能得到的出栈序列有多少种？写出全部的可能序列。24.设某棵三叉树中有40个结点，则该三叉树的最小高度为（）A、3B、4C、5D、625.在线索化二叉树中，t所指节点没有左子树的充要条件是（）A、t-＞left=NULLB、t-＞ltag=1C、t-＞ltag=1且t-＞left=NULLD、以上都不对26.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。A、 15B、 16C、 17D、 4727.简述多关键字文件的作用。28.设有森林 B=（D，S），     D={A，B，C，D，E，F，G，H，I，J}， r∈S  r={〈A，B〉，〈A，C〉，〈A，D〉，〈B，E〉，〈C，F〉，〈G，H〉，〈G，I〉，〈I，J〉}  请回答：画出与森林对应的二叉树的逻辑结构图示。29.有回路的有向图不能完成拓扑排序。30.编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。31.数据结构里，关于遍历二叉树描述正确的是（）。A、二叉树不可以被遍历B、二叉树的遍历方式有：先序遍历、中序遍历、后序遍历、按层次遍历C、二叉树的特殊形式如只有左子树的情况，是不能遍历的D、完全二叉树是不能进行遍历的32.从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为（）。A、归并排序B、选择排序C、交换排序D、插入排序33.栈的插入和删除操作在（）。A、栈底B、栈顶C、任意位置D、指定位置34.分块查找（索引查找）35.按照二叉树的定义，具有3个结点的二叉树有（）种。36.对下列二叉树进行前序遍历的结果为（） A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ37.结点的带权路径长度38.子串在主串中的位置指的是该子串的最后一个字符在主串中的位置。39.向量、栈和队列都是（）结构，可以在向量的（）位置插入和删除元素；对于栈只能在（）插入和删除元素；对于队列只能在（）和（）删除元素。40.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[1..（n（n+1））/2]中，则在B中确定aij（i＜j）的位置k的关系为（）。A、i*（i-1）/2+jB、j*（j-1）/2+iC、i*（i+1）/2+jD、j*（j+1）/2+i41.利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行（）元素间的比较。A、4次B、5次C、7次D、10次42.试用权集合{12，4，5，6，1，2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。43.已知关键码序列为（Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec），散列表的地址空间为0~16，设散列函数为H（x）=，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。44.在索引表中，每个索引项至少包含（）和（）等信息45.已知下列各种初始状态（长度为n）的元素，试问当利用直接插入排序进行排序时，至少需要进行多少次比较（要求排序后的记录由小到大顺序排列）？ ⑴关键码从小到大有序（key1…>keyn）。 ⑶奇数关键码顺序有序，偶数关键码顺序有序（key1<key3<…，key2key4…）。 ⑷前半部分元素按关键码顺序有序，后半部分元素按关键码顺序有序，即：（key1<key2<…<keym，keym+1< keym+2<…）46.括号匹配算法中，扫描到左括号要进栈，扫描到右括号要（）。A、出栈B、进栈C、不操作D、以上都不对47.画出广义表的头尾链表存储结构。48.关于特殊二叉树的遍历，下列选项中说法正确的是（）。A、完全二叉树不能进行遍历B、完全二叉树可以进行遍历C、完全二叉树不可以进行遍历D、满二叉树不是完全二叉树49.在具有n个单元的循环队列中，队满时共有（）个元素。50.假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack（tws）、入栈push（tws，i，x）和出栈pop（tws，i）的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么有缺点。51.设语句x++的时间是单位时间，则以下语句的时间复杂度为（） A、O（1）B、O（n2）C、O（n）D、O（n3）52.表达式求值算法需要两个栈，它们分别是下列哪些（），分别用于存储数据和符号。A、数据栈B、符号栈C、中间结果栈D、汉字栈53.数据结构里，结构体数组的下标不是从（）开始的。A、0B、1C、2D、354.稀疏矩阵一般的压缩存储方法有两种，即（）。A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表55.连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。56.利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（）。57.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。58.串是一种特殊的线性表，其特殊性体现在（）A、可以顺序存储B、数据元素是一个字符C、可以链式存储D、数据元素可以是多个字符59.一个子串在包含它的主串中的位置是指（）。A、子串的最后那个字符在主串中的位置B、子串的最后那个字符在主串中首次出现的位置C、子串的第一个字符在主串中的位置D、子串的第一个字符在主串中首次出现的位置60.线索链表中的rtag域值为（）时，表示该结点无右孩子，此时（）域为指向该结点后继线索的指针。61.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是冒泡算法，最费时间的是（）算法。62.由二叉树的后序和（）遍历序列，可以唯一确定一棵二叉树。63.单链表的主要优点是（）A、便于随机查询B、存储密度高C、逻辑上相邻的元素在物理上也是相邻的D、插入和删除比较方便64.已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。 65.直接选择排序是一种稳定的排序方法。66.数据元素是数据的基本的单位，它（）A、只能有一个数据项组成B、至少有二个数据项组成C、可以是一个数据项也可以由若干个数据项组成D、至少有一个数据项为指针类型67.下图为一棵3阶B-树。在该树上插入元素的B-树是（）。 A、aB、bC、cD、d68.线性结构之队列的应用包括哪些（）。A、消息的缓存B、操作系统的作业调度C、离散事件的模拟D、进制转换69.下列选项中是定义结构体类型的指针变量的格式不正确的是（）。A、struct结构名指针变量名B、struct结构名变量名C、static结构名指针变量名D、struct指针变量名结构名70.数据的存储结构被分为（）、（）、（）和（）四种。71.散列表表长m=14，散列函数为h（k）=k%11，表中已有4个记录，如果用二次探测再散列处理冲突，关键字为49的记录的存储地址是（）。 A、8B、3C、5D、972.当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为（）A、 N-2B、 N-1C、 ND、 N+173.若要把n个顶点连接为一个连通图，则至少需要（）条边。A、 nB、 n+1C、 n-1D、 2n74.对有18个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为（）。A、 1、2、3B、 9、5、2、3C、 9、5、3D、 9、4、2、375.在n个结点的单链表中，查找第i个元素，和修改第i个元素的时间复杂度都是（）。A、O（1）B、O（n）C、O（nn）D、都不对76.下述几种排序方法中，要求内存最大的是（）。A、希尔排序B、快速排序C、归并排序D、堆排序77.编写一个算法判断s2是否是s1的子串。78.在循环双链表的p结点之后插入s结点的操作是（）A、AB、BC、CD、D79.假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K%7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为（）80.在完全二叉树中，若一个结点是叶子结点，则它没有（）A、兄弟结点B、父结点C、左子结点和右子结点D、左子结点、右子结点和兄弟结点81.什么是顺序表？什么是栈？什么是队列？82.当各边上的权值（）时，BFS算法可用来解决单源最短路径问题。A、均相等B、均互不相等C、不一定相等D、均相等或均不等83.程序越短，程序运行的时间就越少。84.S="morning"，执行求子串函数SubStr（S，2，2）后的结果为（）。A、"mo"B、"or"C、"in"D、"ng"85.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。86.假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f2，设顺序表L=（3，7，3，2，1，1，8，7，3），写出执行算法f2后的线性表L的数据元素，并描述该算法的功能。voidf2（SeqList*L）{inti，j，k；k=0；for（i=0；ilength；i++）{for（j=0；jdata[i]!=L->data[j]；j++）；if（j==k）{if（k!=i）L->data[k]=L->data[i]；k++；}}L->length=k；}87.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。A、8B、63.5C、63D、788.线性结构中数据元素的位置之间存在（）的关系。A、一对一B、一对多C、多对多D、每一个元素都有一个直接前驱和一个直接后继89.画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。 （1）A=（（）） （2）B=（a，b，c） （3）C=（a，（b，（c））） （4）D=（（a，b），（c，d）） （5）E=（a，（b，（c，d）），（e）） （6）F=（（a，（b，（），c），（（d），e）））90.采用三元组表存储稀疏矩阵，是为了（）。A、节省存取时间B、节省存储空间C、提高对矩阵元素的访问速度D、提高对矩阵运算的可靠性91.如果结点A有3个兄弟，B是A的双亲，则结点B的度是（）。A、1B、2C、3D、492.已知如下图所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。 A、abecdfB、acfebdC、aebcfdD、aedfcb93.（）中任何两个结点之间都没有逻辑关系。A、集合B、图状结构C、树型结构D、线性结构94.一个算法应该是（）。A、程序B、问题求解步骤的描述C、要满足五个基本特性D、A和C95.在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序96.设有二维数组a[5][6]，每个元素占相邻的8个字节，存储器按字节编址，已知a的起始地址是1000，试计算按行序优先时，元素a[3][5]的起始地址。97.简述树、二叉树、满二叉树和完全二叉树的结构特性。98.广义表运算式HEAD（TAIL（（a，b，c），（x，y，z）））的结果是：（）。99.设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为（）。100.（）既对数据施加的操作。第I卷参考答案一.参考题库1.参考答案： 2.参考答案： a.（11）（3）（14） b.（10）（12）（8）（3）（14） c.（10）（12）（7）（3）（14） d.（12）（11）（3）（14） e.（9）（11）（3）（14）3.参考答案：334.参考答案：算法设计如下： 5.参考答案：1，2，4，8，3，5，96.参考答案：3*2+*57.参考答案：8.参考答案：正确9.参考答案：B10.参考答案：将哨兵设置在下标高端，表示从数组的低端开始查找，在查找不成功的情况下，算法自动在哨兵处终止。具体算法如下： 11.参考答案：高级语言12.参考答案：错误13.参考答案：B14.参考答案：正确15.参考答案：B16.参考答案：有向图17.参考答案：删除p的后继结点18.参考答案：O（1）19.参考答案：C20.参考答案：C21.参考答案：A,B,C22.参考答案：计算机语言23.参考答案：24.参考答案：B25.参考答案：B26.参考答案：B27.参考答案：多关键字文件是既包含主关键字索引、又包含多个次关键字索引的文件。在实际中，不仅会根据主关键字做查找，同时也会根据一系列次关键字做查找，此时使用多关键字文件可以提高查找效率。28.参考答案： 29.参考答案：正确30.参考答案： voidlinklist_c（Lnode*heaD. {Lnode*p；p=head； if（!p）returnERROR； while（p->next!=NULL） p=p->next； p->next=head； } 设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。31.参考答案：B32.参考答案：D33.参考答案：B34.参考答案： 分块查找以前两个为基础，将待查记录分成若干块，每块的关键字无序，但每块的关键字的最大值有序，查找时，先查找到待查记录所在的块，再在块内进行顺序查找。找块时，即可以用折半查找，也可用顺序查找。35.参考答案：536.参考答案：C37.参考答案： 该结点到树根之间的路径长度与结点上权的乘积。38.参考答案：错误39.参考答案：线性任何栈顶队尾队首40.参考答案：B41.参考答案：A42.参考答案： WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=6943.参考答案：H.Jan）=10/2=5，H（Feb）=6/2=3，H（Mar）=13/2=6，H（Apr）=1/2=0 H.May）=13/2=6，H（Jun）=10/25，H（Jul）=10/25，H（Aug）=1/2=0 H.Sep）=19/2=8，H（Oct）=15/2=7，H（Nov）=14/2=7，H（Dec）=4/2=2 采用线性探测法处理冲突，得到的闭散列表如下： 平均查找长度=（1+1+1+1+2+4+5+2+3+5+6+1）/12=32/12 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=（1×7+2×4+3×1）/12=18/12 44.参考答案：关键码；关键码对应的记录在存储器中的位置45.参考答案：依题意，最好情况下的比较次数即为最少比较次数。 ⑴插入第i（2≤i≤n）个元素的比较次数为1，因此总的比较次数为：1+1+……+1=n-1 ⑵插入第i（2≤i≤n）个元素的比较次数为i，因此总的比较次数为：2+3+……+n=（n-1）（n+2）/2 ⑶比较次数最少的情况是所有记录关键码按升序排列，总的比较次数为：n-1 ⑷在后半部分元素的关键码均大于前半部分元素的关键码时需要的比较次数最少，总的比较次数为：n-146.参考答案：A47.参考答案：48.参考答案：B49.参考答案：n-150.参考答案： 51.参