北京工业大学计算机科学与技术895计算机学科专业基础2013年数据结构

–
运算处理

内容：建表、插入、删除、输出； 实现：利用指针变量作为函数参数，传递 线性表地址；
•void CreateList (SequenList *L) { • int n, i, mydata;
• printf("\nPlease input total number of data item\n");


int exp;
struct polyterm *next;

} TERM;

10．设有编号为1，2，3，4的四辆列车，顺序 进入一个栈式结构的车站，具体写出这四辆列 车开出车站的所有可能的顺序。


1， 2， 3， 4 1， 3， 4， 2 2， 1， 4， 3 2， 4， 3， 1 3， 4， 2， 1
–
人—机交互部分

内容：通过屏幕提示功能选择菜单； 通过键盘输入实现功能的选择； 要求：提示内容清晰易读，

键盘操作简单准确；

实现：循环扫描键盘，等待用户输入；
根据输入内容确定要执行的分支程序。










int main( ) { SequenList MyList,*L; char cmd; int i, t, x; L=&MyList; L->last=-1; do { do { clrscr( ); printf("\n\t c, C......Create List\n"); printf("\n\t i, I .....Insert"); printf("\n\t d, D......Delete"); •while •While ((cmd!='d')&&(cmd!='D')&& ((toupper(cmd)!='D')&& printf("\n\t q, Q......Quit\n\tYour choice:"); (cmd!='q')&&(cmd!='Q')&& (toupper(cmd)!='Q')&& cmd=getchar( );

已知一个图的顶点集 V 和边集 E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4. 画出向小根堆中加入数据 4, 2, 5, 8, 3 时，每加入一个数据后堆的变化。 四、阅读算法（每题 7 分，共 14 分） 1. LinkList mynote(LinkList L) {//L 是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； 3. L； } 请回答下列问题： （1）说明语句 S1 的功能； （2）说明语句组 S2 的功能； （3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性 表。 2. void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout<<BT->data<<' '; } } 该算法的功能是：
数据结构试卷（二）
一、选择题(24 分) 1．下面关于线性表的叙述错误的是（ ） 。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共 有（ ）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 3．设顺序循环队列 Q[0：M-1]的头指针和尾指针分别为 F 和 R，头指针 F 总是指向队头元素 的前一位置，尾指针 R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为 （ ） 。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为 CABD，则后序遍历该二叉树 得到序列为（ ） 。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5．设某完全无向图中有 n 个顶点，则该完全无向图中有（ ）条边。 2 2 (A) n(n-1)/2 (B) n(n-1) (C) n (D) n -1 6．设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（ ） 。 (A) 9 (B) 10 (C) 11 (D) 12 7．设某有向图中有 n 个顶点，则该有向图对应的邻接表中有（ ）个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字 5 为基准进行一趟快 速排序的结果为（ ） 。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8

北京工业大学1999年硕士研究生入学考试试题考试科目：数据结构一、（26分）填空、选择（一个或多个）题，1-6题每小题2分：1下面的叙述中，不正确的是（）A关键活动不按期完成就会影响整个工程的完工时间。

B任何一个关键工程提前完成，将使整个工程提前完成。

C所有关键活动都提前完成，则使整个工程提前完成。

D提些关键活动若提前完成，则将使整个工程提前完成。

2 下面的排序算法中，不稳定得是（）A 起泡排序B 折半插入排序C简单选择排序D希尔排序E基数排序F堆排序。

3包含结点A，B，C的二叉树有-----------种不同的状态，---------种不同的二叉树。

4包含结点A，B，C的树有------种不同形态，------种不同的树。

5分块检索中，若索引表和各块内存均用顺序查找，则有900各元素的线性表分成-----块最好：若分成25块；其平均查找长度为--------。

6下面的程序段中，对ｘ的赋值语句的频度为------------（表示为n的函数）ＦＯＲ Ｉ：＝ １ＴＯ Ｎ ＤＯＦＯＲ Ｊ：＝１ ＴＯＩ ＤＯＦＯＲ Ｋ：＝Ｉ ＴＯ Ｊ ＤＯ ｘ：＝ｘ＋ＤＥＬＴＡ；７（８分）设有字符序列Ｑ Ｈ Ｃ Ｙ Ｐ Ａ Ｍ Ｓ Ｒ Ｄ Ｆ Ｘ要求按字符升列排序：采用初是长为４的希尔（３ｂｅｌｌ）排序，一趟扫描的结果是――――――――― 采用以元素为分界元素的快速排序，一躺扫描的结果是------------。

8（6分）已知广义表：A-（0），B-（），C-（a，b，c，d），D-（A，B，C）它们的存储结构图为（接两种结构种的任一种即可）：二（6分）编写递归程序将二叉树逆时针旋转90度打印出来。

如右图：（要求用类PASCAL 语言，并描述结构）。

三 （8分）用依次输入的关键字13，29，41，19，5，1，7和6建一棵三阶B-树，画出建该树的变化过程示意图（每插入一个结点至少用一张图）。

四（共20分）已知顶点1——6和输入边与权值的序列（如右框中）： 2 4 6 每行三个数表示一条边的两个端点和其权值，共11行。

delete(Dt,A) 初始条件：字典 Dt 存在，A 是字典元素 操作结果：删除数据 A
find(Dt,A) 初始条件：字典 Dt 存在，A 是字典元素 操作结果：查找字典数据，返回位置信息
（2）链式存储结构，方便更新
第 5 页 共 16 页
友情提供，请勿传播，谢谢合作--------picco
2006 真题答案
一．选择题 ADCBD 二．填空题 1.O(nu+tu) 三．解答题
2.A GOOD STUDENT
3.7、11、13、14
4.直接插入排序
4（1）35%13=9， h1(35)=35%11+1=13 H2(35)=(9+2*3)%11=4 四．抽象数据类型设计题
ADT dictionary{ 数据对象 D：D 是具有相同特性的数据元素的集合，每个元素由两部分组成，分别为关键码和属
2空间上直接插入排序不需额外的空间快速排序需要递归工作栈所以直接插入排序的空间性能更好时间上序列长度较小因为两个子序列分别有序直接插入排序比较次数较少但快速排序在序列基本有序时效率反而下降所以直接插入排序时间性能更好四
友情提供，请勿传播，谢谢合作--------picco
说明：此答案是我考研时所做，先整理出来，正确率足够使用，但不保证所有题都正确，请按自己的 情况酌情处理。另外我没有公开此档案，希望拿到的同学不要传播（我直接的朋友可以传给自己的真实同 学，但请间接朋友不要继续往下传），不要宣传从我这里得到，毕竟这样的独家资料对你们也有好处。这 份资料价值很高，我整理也很费劲，所以请尊重我的劳动。真题可以从王道论坛下载，从 1995 年的开始， 但我建议从 2003 年开始看，因为以前的题太旧了，跟现在的考试风格差别很大，所以我的答案也是从 03 年开始的。