西南交通⼤学2006年硕⼠研究⽣⼊学考试试卷西南交通⼤学2006年硕⼠研究⽣⼊学考试试卷试题代码：412试题名称：程序设计及数据结构考⽣注意：1.本试题共6⼤题，共9页，考⽣请认真检查；2.请务必将答案写在答卷纸上，写在试卷上的答案⽆效。
题号⼀⼆三四五六七⼋九⼗总分得分签字⼀、填空题(本⼤题共20⼩题，每⼩题1分，共20分)1、若有定义：int a=2,b=2；则计算表达式a+=a*=b-=a之后，a的值是。
2、若有定义：inta[3]={3,13,56},*p=a,*q=a；则表达式：(*++p)+(++*q)的值是。
3、若有如下定义：int y=319,z=3；则下列表达式的值是：(’E’/y*1000) ; (z=2*3,z*5,z*8) ;4、若有宏定义：#define MYFUNC(x,y)(x>y?x:y)则MYFUNC(3,7)的值是。
5、在平⾯坐标系中，点A的坐标是(x1,y1)，点B的坐标是(x2,y2)，则表⽰A与B的距离的C 语⾔表达式是。
6、C语⾔中构造数据类型有：。
7、C语⾔存储字符串时，⽤特殊的字符表⽰字符串的结束。
8、定义C函数时，若函数没有返回值，则返回值类型应设为。
9、⽤数组名作为函数调⽤时的实参，实际上传送给形参的是。
10、以下程序运⾏后，输出结果是。
void main(void){ int i ,Sum;for(i=0;i<=100;i++){ Sum=0;Sum=Sum+i;}printf(“%d”,Sum);}11、数据结构中，处理数据的最⼩单位为。
a.数据b.数据项c.数据对象d.数据元素e.基本数据类型12、n个节点的⼆叉树最⼤深度为；最⼩深度为。
13、⼆叉排序树的查找时间复杂度为；最坏情形的查找⽐较次数为。
14、平衡⼆叉树是⼆叉树吗？（Yes or No）。
15、平衡⼆叉树左右⼦树深度之差的绝对值⼩于。
16、平衡⼆叉树的查找算法思想与折半查找算法思想⼀样吗？。
数据结构考研真题及其答案完整版数据结构是计算机科学与技术领域中的一门重要课程，也是计算机考研中必考的一门科目。
通过研究数据结构，可以帮助我们更好地理解和应用计算机算法，提高计算机程序的效率和性能。
为了帮助考生更好地备考数据结构，本文将分享一些数据结构考研真题及其答案，供考生参考。
一、选择题1. 下列关于栈的叙述中，错误的是（）A. 栈是一种线性数据结构，具有后进先出（LIFO）的特点B. 栈可以用数组实现，也可以用链表实现C. 栈的插入和删除操作都是在同一端进行的D. 栈的插入和删除操作的时间复杂度都是O(1)答案：C解析：栈的插入操作叫做入栈，删除操作叫做出栈。
入栈和出栈操作都是在栈顶进行的，而不是同一端。
2. 假设要对n个整数关键字进行排序，以下排序算法中，平均时间复杂度最小的是（）A. 冒泡排序B. 快速排序C. 归并排序D. 直接插入排序答案：C解析：归并排序的时间复杂度是O(nlogn)，平均时间复杂度最小。
二、填空题1. 下列关于图的遍历顺序的说法中，正确的是：深度优先搜索访问的顺序是________，广度优先搜索访问的顺序是________。
答案：前序遍历，层次遍历解析：深度优先搜索即前序遍历，广度优先搜索即层次遍历。
2. 给定一个最小堆，若删除堆顶元素后，需要对堆进行调整，所采用的操作是________。
答案：下滤解析：删除堆顶元素后，将最后一个叶子节点放到堆顶，然后进行下滤操作。
三、简答题1. 请简要说明动态规划算法的基本思想和应用场景。
答：动态规划算法的基本思想是将问题分解为多个子问题，通过求解子问题的最优解来得到原问题的最优解。
它通常适用于具有重叠子问题和最优子结构性质的问题。
动态规划算法可以大大减少问题的重复计算，提高算法的效率和性能。
它在求解最短路径、最长公共子序列、背包问题等具有广泛的应用。
2. 请简要介绍红黑树的特点和应用场景。
答：红黑树是一种自平衡的二叉查找树，它具有以下特点：1) 每个节点都有一个颜色，红色或黑色；2) 根节点是黑色的；3) 叶子节点（NIL节点）都是黑色的；4) 如果一个节点是红色的，则它的两个子节点都是黑色的；5) 从根节点到叶子节点的路径上，不同路径上黑节点的个数相同。
一、填空题（前17空每1分，后面4空每空2分，共25分）1. 根据数据元素之间关系的不同特性，通常有四类基本结构，即：集合、线性结构、树形结构和(1) 结构。
2. 数据类型是一个值的集合和定义在这个值集上的一组(2) 的总称。
3. 算法的性能主要由时间复杂度和(3) 复杂度表示。
4. 队列的操作特点是“先进先出”，堆栈的操作特点是(4) 。
5. 用长度为m个元素的C语言数组实现循环队列，若f, r分别表示队头和队尾下标, 其中队头下标指向队头元素，队尾下标指向队尾元素后面的一个空闲位置，入队方向为下标加1方向，则在少用一个元素空间的前提下，队满的判断条件是(5) 。
6. 拥有100个结点的完全二叉树中，叶子结点数是(6) 。
7. 广义表A=((), (a))，则HEAD(A)= (7) ，TAIL(A)= (8) 。
8. 若20行×20列的下半三角矩阵(含主对角线元素)采用一维数组A以列序为主序顺序存储各元素。
假设矩阵以及一维数组下标均从0开始，则一维数组元素A[121]在矩阵中对应元素的行下标是(9) ，列下标是(10) 。
9. 已知两个带附加头结点的单链表，每个链表的数据结点按升序连接，下面的函数不另辟存储空间，实现将两个升序单链表归并为一个升序单链表，请填空。
已知结点结构定义为typedef struct node { int data; struct node *next; } LNode;LNode *merge(LNode *h1, LNode *h2) // h1, h2传入两个升序链表的附加头结点的指针{ p1=h1->next; p2=h2->next;last=h1; delete h2; //附加头结点*h1作为归并后的链表附加头结点while( (11) ){ if(p1->data (12) p2->data){ last->next=p1; p1=p1->next; }else{ last->next=p2; p2=p2->next; }last= (13) ;}if(p1) last->next=p1;if(p2) last->next= (14) ;return h1;}10. 若二叉树结点指针类型定义如下：typedef struct bt_node { int data; struct bt_node *left, *right; } *BT;下面的C++函数用先根遍历算法将所有叶子结点按right指针域从左向右串接成单向链表，请填空。
数据结构考研笔记整理（全）一、第二章线性表●考纲内容●一、线性表的基本概念●线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑结构，实现线性表的存储结构为顺序表或者链表●二、线性表的实现●1、顺序表●定义(静态分配)●#define MaxSize 50 \\ typedef struct{ \\ ElemType data[MaxSize];\\ intlength;\\ }SqList;●定义(动态分配)●#define MaxSize 50\\ typedef strcut{\\ EleType *data; //指示动态非配数组的指针\\ int MaxSize,length;\\ }SqList;●c的动态分配语句为L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);●c++动态分配语句为L.data=new ElemType[InitSize];●插入操作●删除操作●按值寻找●2、链表●单链表●单链表的定义●●头插法建立单链表●●尾插法建立单链表●●按序号查找getElem(LinkList L,int i)和按值查找locateElem(LinkListL,ElemType e)●插入结点（后插）●p=getElem(L,i-1); //查找插入位置的前驱结点\\ s.next=p.next;\\p.next=s;●将前插操作转化为后插操作,即先将s插入的p的后面然后调换s和p的数据域●s.next=p.next;\\ p.next=s.next;\\ temp=p.data;\\ p.data=s.data;\\s.data=temp;●删除结点●p.getElem(L,i-1);\\ q=p.next;\\ p.next=q.next;\\ free(q);●双链表（结点中有prior指针和next指针）●循环链表●静态链表●借助数组来描述线性表的链式存储结构，结点中的指针域next为下一个元素的数组下标●三、线性表的应用●使用的时候如何选择链表还是顺序表？●表长难以估计，经常需要增加、删除操作——链表;表长可以估计，查询比较多——顺序表●链表的头插法，尾插法，逆置法，归并法，双指针法；顺序表结合排序算法和查找算法的应用●小知识点（选择题）二、第三章栈，队列和数组●考纲内容●一、栈和队列的基本概念●栈：后进先出，LIFO，逻辑结构上是一种操作受限的线性表●队列：先进先出，FIFO，逻辑结构上也是一种操作受限的线性表●二、栈和队列的顺序存储结构●栈的顺序存储●●队列的顺序存储●进队：队不满时，送值到队尾元素，再将队尾指针加一●出队：队不空时，取队头元素值，再将队头指针加一●判断队空：Q.front==Q.rear==0;●循环队列（牺牲一个单元来区分队空和队满，尾指针指向队尾元素的后一个位置，也就是即将要插入的位置）●初始：Q.front==Q.rear●队满：(Q.rear+1)%MaxSize=Q.front●出队，队首指针进1:Q.front=(Q.front+1)%MaxSize●入队，队尾指针进1:Q.rear=(Q.rear+1)%MaxSize●队列长度：(Q.rear+MaxSize-Q.front)%MaxSize●三、栈和队列的链式存储结构●栈的链式存储●●队列的链式存储●实际是上一个同时带有头指针和尾指针的单链表，尾指针指向单链表的最后一个结点，与顺序存储不同,通常带有头结点●四、多维数组的存储●行优先：00，01，02，10，11，12●列优先：00，10，01，11，02，12●五、特殊矩阵的压缩存储●对称矩阵●三角矩阵●三对角矩阵（带状矩阵）●稀疏矩阵●将非零元素及其相应的行和列构成一个三元组存储●十字链表法●六、栈、队列、数组的应用●栈在括号匹配中的应用●栈在递归中的应用●函数在递归调用过程中的特点：最后被调用的函数最先执行结束●队列在层次遍历中的应用●二叉树的层次遍历●1跟结点入队●2若队空，则结束遍历，否则重复3操作●3队列中的第一个结点出队并访问，若有左孩子，则左孩子入队；若有右孩子，则右孩子入队●重点为栈的(出入栈过程、出栈序列的合法性)和队列的操作及其特征●小知识点(选择题)●n个不同元素进栈，出栈元素不同排列的个数为{2n\choose n }/(n+1)●共享栈是指让两个顺序栈共享一个存储空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，可以更有效的利用存储空间，同时对存储效率没有什么影响●双端队列是指允许两端都可以进行入队和出队操作的队列●输出受限的双端队列：允许两端插入，只允许一端删除●输入受限的双端队列：允许两端删除，只允许一端插入三、第四章串●考纲内容●字符串模式匹配●暴力算法●注意指针回退时的操作是i=i-j+2;j=j+1;●kmp算法●手工求next数组时，next[j]=s的最长相等前后缀长度+1，其中s为1到j-1个字符组成的串●在实际kmp算法中，为了使公式更简洁、计算简单，如果串的位序是从1开始的，则next数组需要整体加一；如果串的位序是从0开始的，则next数组不需要加一●根据next数组求解nextval数组：如果p[j]==p[next[j]]，则nextval[j]=nextval[next[j]]，否则nextval[j]=next[j];●小知识点●串和线性表的区别：1线性表的数据元素可以不同，但串的数据元素一般是字符；2串的操作对象通常是子串而不是某一个字符四、第五章树与二叉树●考纲内容●一、树的基本概念●定义●树是一种递归的数据结构，是一种逻辑结构●树的性质●结点数为n，则边的数量为n-1●树中的结点数等于所有结点的度数之和加1（一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度，每一条边表示一个结点，对应一个度，只有根结点上面无边，故结点树=度数之和+1）●度为m的树中第i层至多有m^{i-1}个结点（i\geq1）（m叉树的第i层最多有m^{i-1}个结点）●高度为h的m叉树至多有(m^h-1)/(m-1)个结点（假设每一个结点都有m个孩子，则由等比数列的求和公式可以推导出该式子）●具有n个结点的m叉树的最小高度是\lceil log_m(n(m-1)+1)\rceil（由高度为h的m叉树的最大结点树公式有，n满足式子(m^{h-1}-1)/(m-1) \leq n\leq (m^h-1)/(m-1)）●高度为h的m叉树至少有h个结点；高为h，度为m的树至少有h+m-1个结点（m叉树并不等于度为m的树，m叉树可以为空树，要求所有结点的度小于等于m，而度为m的树一定有一个结点的度数为m）●二、二叉树●二叉树的定义及其主要特征●定义●特点●每个结点至多只有两颗子树●二叉树是有序树，其子树有左右之分，次序不能颠倒，否则将成为另一颗二叉树，即使树中结点只有一颗子树，也要区分他是左子树还是右子树●特殊的二叉树●满二叉树：高度为h，结点数为2^h-1，所有叶子结点都集中在二叉树的最下面一层，除叶子结点外的所有结点度数都为2，从根结点为1开始编号，对于编号为i的结点，其父结点为\lfloor i/2 \rfloor，左孩子(若有)编号为2i，右孩子(若有)编号为2i+1，所以编号为偶数的结点只可能是左孩子，编号为奇数的结点只可能是右孩子●完全二叉树：删除了满二叉树中编号更大的结点，高为h，结点数为n的完全二叉树的每个结点的编号都与高度为h的满二叉树中编号为1到n的结点相同。
