《2022年北航数据结构与程序设计真题北航真题及答案.docx》由会员分享，可在线阅读，更多相关《2022年北航数据结构与程序设计真题北航真题及答案.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品_精品资料_20XX年“数据结构与 C 程序设计 ”代码 991试题一、单项挑选题（此题共20分,每道题各2 分）1 对于长度为n 的线性表,建立其对应的单链表的时间复杂度为 .A O1 . B Olog2n. On . D On2 .2 一般情形下,在一个双向链表中插入一个新的链结点, .A 需要修改4 个指针域内的指针.B 需要修改3 个指针域内的指针.C需要修改2 个指针域内的指针.D 只需要修改1 个指针域内的指针.3 假设用单个字母表示中缀表达式中的一个运算数 或称运算对象 ,并利用堆栈产生中缀表达式对应的后 缀表达式.对于中缀表达式A+B*C/D-E,当从左至右扫描到运算数E
2、时,堆栈中的运算符依次是 . 注：不包含表达式的分界符A +*/-. B +*/-. C+*-. +*-.4 如某二叉排序树的前序遍历序列为50,20,40,30,80,60,70,就后序遍历序列为 .A 30,40,20,50,70,60,80. B 30,40,20,70,60,80,50.C70,60,80,50,30,40,20. D 70,60,80,30,40,20,50.5 分别以 6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼Huffman树的深度为 .A 6 . B 5. C4 . D 3 .6 以下关于图的表达中,错误选项 .A 依据图的定义,图中至少有一个
3、顶点.B 依据图的定义,图中至少有一个顶点和一条边 弧 . C具有 n 个顶点的无向图最多有nn-1/2条边. D 具有 n 个顶点的有向图最多有nn-1条边 弧 .7 如在有向图G 的拓扑序列中,顶点vi 在顶点 vj 之前,就以下4 种情形中不行能显现的是 .A G 中有弧 .B G 中没有弧 .CG 中有一条从顶点vi 到顶点 vj 的路径.D G 中有一条从顶点vj 到顶点 vi 的路径.8 以下关于查找操作的表达中,错误选项 .A 在次序表中查找元素可以采纳次序查找法,也可以采纳折半查找法. B 在链表中查找结点只能采纳次序查找法,不能采纳折半查找法.
4、 C一般情形下,次序查找法不如折半查找法的时间效率高.D 折半查找的过程可以用一棵称之为“判定树 ”的二叉树来描述.9 在一棵 m 阶 B- 树中,除根结点之外的任何分支结点包含关键字的个数至少是 .A m/2-1. B m/2 . C m/2-1. D m/2.可编辑资料 - - - 欢迎下载精品_精品资料_10 如对序列 49, 38, 65, 97, 76, 13, 27, 49界元素的最终位置 时,序列的状态是 .进行快速排序,就第一趟排序终止 即确定了第1 个分可编辑资料 - - - 欢迎下载精品_精品资料_A 13, 27, 49 ,
5、 38, 49, 76, 97, 65. B 13, 38, 27, 49 , 49, ,7967, 65.C13, 38, 49 , 27, 49, 97, 76, 65. D 13, 38, 49 , 27, 49, 76, 97, 65.二、填空题 此题共 20 分,每道题各2 分1 非空线性表在采 储备结构的情形下,删除表的一个数据元素平均需要移动表中近一半元素的位置.2 将一个长度为n 的单链表链接到一个长度为m 的单链表后面, 该算法的时间复杂度用大O 符号表示为 .3 如完全二叉树的叶结点的数目为k ,且最下面一层的结点数大于1 ,就该完全二叉树的深度为 .可编辑资料 - - -
6、 欢迎下载精品_精品资料_4 如深度为8 的完全二叉树的第7 层有 10 个叶结点,就该二叉树的结点总数为 .5 在具有 n 个顶点的有向图中,每个顶点的度最大可以达到 .6 如对有向图进行拓扑排序,就能够得到拓扑序列的条件是 .7 已知长度为10 的次序表中数据元素按值从小到大排列.如在该表中进行折半查找, 就平均查找长度ASL是 .8 如在一棵 m 阶 B- 树的某个结点中插入一个新的关键字值而引起结点产生分裂,就该结点中原有的关键字值的数目是 .9 有一种排序方法可能会显现这种情形：最终一趟排序开头之前,序列中全部的元素都不在其最终应当在的位置上,这种排序方法是 .10 如依据泡排序法的
7、思想将序列2, 12, 16, 5, 10中元素按值从小到大进行排序,整个排序过程中所进行的元素之间的比较次数为 .三、综合题 此题共 20 分,每道题各5 分1 一般情形下, 当一个算法中需要建立多个堆栈时可以选用以下三种处理方案之一.问：这三种方案之间相比较各有什么优点和缺点？（1 ）多个堆栈共享一个连续的储备空间.（2 ）分别建立多个采纳次序储备结构的堆栈.（3 ）分别建立多个采纳链式储备结构的堆栈.2 已知二叉树采纳二叉链表储备结构,根结点指针为T,链结点类型定义为： typedef struct nodechar data;/*数据域*/struct node *lchild, *r
8、child;/*指向左、右子树的指针域*/ *BTREE.下面的算法的功能是输出二叉树中全部叶结点的数据信息.请在算法的空白处 符号 -处 填入合适内容,使算法完整. void FUNCBTREE TifT.=NULL if-printf“ %c”-,dTata;FUNC-;FUNC-;3 对给定 AOE 网 如题三 3 图所示 ,请完成（1 ）分别求出各活动aii=1, 2, 14 的最早开头时间与最晚开头时间. 以表格形式给出结果（2 ）求出全部关键路径. 请以图形方式画出各关键路径（说明：由于题三3 图在本网站内无法显示,可参见指定教材p280页 8-16题）4 已知要将给定的关键字值序
9、列42, 51, 16, 26, 50, 25, 37, 68, 64, 33, 18进行散列储备,并且要求装填因子 也称负载因子 0.61 ,（1 ）请利用除留余数法构造出合适的散列函数.（2 ）请画出利用该散列函数依次将序列中各关键字值插入到散列表以后表的状态.设散列表初始为空,并且采纳线性探测再散列法处理散列冲突.四、算法设计题（此题15 分 ）可编辑资料 - - - 欢迎下载精品_精品资料_假设长度为 n 的次序表A1.n中每个数据元素为一整数,请写出依据以下思想将表中数据元素按值从小到大进行排序的算法：第1 趟排序将最小值元素放在A1 中,最大值元素放在 An 中.第 2 趟排序将次
10、小值元素放在A2 中,次大值元素放在An-1中.,依此下去,直至排序终止.五、填空题 此题共 20 分,每道题各2 分1 已知某等比数列的第一项a1 为 1 ,公比为 3 ,以下程序的功能是输出该数列中小于1000的最大项 an及其对应的 n .请在程序的空白处 符号 -处 填入合适内容,使程序完整. main int n=1, a=1, q=3; while1a=a*q; n+; ifa=1000-;printf“ n=%d,a=%d n” , n-1, -;2 以下递归函数FUNC2 的功能是判定整型数组an 是否为递增数组,即判定数组的元素是否按值从小到大排列.如是一个递增数组,就函数返
11、回true ,否就,函数返回false .请在函数的空白处 符号 -处 填入合适内容,使函数完整. bool FUNC2int a , int nifn=1return true; ifn=2return -;return - & an-1=an-2;3 以下程序的功能是主函数调用FUNC3 函数求方阵a 中两条对角线上元素之和.请在程序的空白处 符号 -处 填入合适内容,使程序完整.#define N 10void FUNC3int aNN, int *p, int *qint i;*p=0;*q=0;fori=0; iN; i+*p=*p+*-;*q=*q+*-;main int aNN,
12、 i, j, x, y; fori=0; iN; i+可编辑资料 - - - 欢迎下载精品_精品资料_forj=0; jN; j+scanf“ %d” , *a+i+j;FUNC3a, &x, &y; /* x, y 中分别存放主对角线与副对角线上的元素之和*/ printf“ %d, %dn” , x, y;4 以下程序的功能是先通过键盘输入一正整数,然后调用一递归函数FUNC4 ,该函数将正整数转换为对 应的数字字符组成的字符串显示在屏幕上.例如：如输入的正整数为583 ,就屏幕上显示的是字符串583 .请在程序的空白处 符号 -处 填入合适内容,使程序完整.#include void F
13、UNC4int nint i; i=n/10; if-FUNC4i;putchar-;可编辑资料 - - - 欢迎下载精品_精品资料_main int n; printf请“输入一正整数n ： ” ;可编辑资料 - - - 欢迎下载精品_精品资料_scanf“ %d” , &n;printf转“换后的字符串是：” ;FUNC4n;5 以下程序的功能是将小写字母转换成对应的大写字母后的第2 个字母,例如,将a 转换成 C,将 b 转换成 D,其中, y 转换成 A ,z 转换成 B .请在程序的空白处 符号 -处 填入合适内容,使程序完整.#include main char ch;whilec
14、h=getchar .=nifch= a & ch Z & ch= Z +2-;6 以下函数FUNC6 的功能是删除字符串s 中的全部空白字符,包括Tab 字符、回车符以及换行符.请在函数的空白处 符号 -处 填入合适内容,使函数完整.#include #include #include FUNC6char *sint i, t;char c80;可编辑资料 - - - 欢迎下载精品_精品资料_fori=0,t=0; si; i+ if.isspace-c-=si; ct=0;strcpys, c;7 以下程序的功能是判定输入的字符串是否是“回文 ”. 注：按次序读与按逆序读都一样的字符串被称
15、为“回文”,例如： abcdcba.请在程序的空白处 符号 -处 填入合适内容,使程序完整.#include #include main char ch81, *p=ch, *q; getsp;q=p+-;while- if*p=*qp+; q-;elsebreak;可编辑资料 - - - 欢迎下载精品_精品资料_ifpqprintf该“字符串不是回文；n” ;可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_elseprintf该“字符串是回文；n” ;可编辑资料 - - - 欢迎下载精品_精品资料_8 以下程序的功能是：对于字符类型变量ch=1
16、08,保留中间两位,而将高、低3 位清零.请在程序的空白处 符号 -处 填入合适内容,使程序完整.main char ch;ch=108; ch=-;printf“ %d” , ch;9 设 file 为存放了整型数据的二进制文件.以下程序的功能是从该文件中读入第3 个数据输出到屏幕上.请在程序的空白处 符号 -处 填入合适内容,使程序完整.#include main FILE *fp;int number;fp=fopen“ file” , “ rb ” ;fseekfp, -, SEEK_SET;fread-, 1, fp;可编辑资料 - - - 欢迎下载精品_精品资料_printf“ %
17、d” , number; fclosefp;10 以下程序的功能是将一个磁盘中的二进制文件复制到另一个磁盘中.两个文件的文件名随命令行一起输入,输入时原有文件的文件名在前,新复制文件的文件名在后.请在程序的空白处 符号 -处 填入合适内容,使程序完整.#include mainint argc, char *argv FILE *old, *new; ifargc.=3printf“ You forgot to enter a filename.n” ;exit0;ifold=fopen-=NULLprintf“ Cannot open infile.n” ; exit0;ifnew=fope
18、n-=NULLp rintf“ Cannot open outfile.n” ; exit0;while.feofold fputcfgetcold, new;fcloseold; fclosenew;六、简答题（此题共20 分,每道题各5 分）1 在 C 语言中,函数调用时数据的传递通常有哪几种方式？2 在 C 语言中,指针可以做哪些运算？3 共用体 union具有哪些基本特点？4 使用文件的基本操作步骤是怎样的？七、程序设计题（此题15 分 ）请编写一程序,该程序的功能是找出并且删除一维整型数组a100中的最小值元素.要求： 1 数组各元素通过键盘输入获得初值.2 全部对数组元素的引用必需
19、通过指针完成.八、程序设计题（此题20 分 ）请仅编写出一C 语言函数 char *maxwordchar *s, char *t,该函数的功能是求出字符串s 与字符串t 的最长公共单词 这里, 假设两个字符串均由英文字母和空格字符组成 .如找到这样的公共单词,函数返回该单词,否就,函数返回NULL .例如：如 s=“This is C programming text”, t= “This is a text for C programming” ,就函数返回 “ programming”.可编辑资料 - - - 欢迎下载精品_精品资料_要求： 1 函数中不得设置储存单词的储备空间.2 给出
20、函数之前请用文字简要表达函数的基本思想.20XX年“数据结构与 C 程序设计 ”代码 991试题参考答案一、单项挑选题1 C2 A3 D4 B5 C6 B7 D8 A9 C10 D二、填空题1 次序2 Om3 log2k+14 2355 2n-16该有向图中不存在回路7 2.98m-19插入排序法10 9三、综合题1 答：（ 1 ）多个堆栈共享一个连续的储备空间,可以充分利用储备空间,只有在整个储备空间都用完时才能产生溢出,其缺点是当一个堆栈溢出时需要向左、右栈查询有无闲暇单元.如有,就需要移动相应元素和修改相关的栈底和栈顶指针的位置.当各个堆栈接近溢出时,查询闲暇单元、移动元
21、素和修改栈底栈顶指针位置的操作频繁,运算复杂,并且耗费时间.（2 ）每个堆栈仅用一个次序储备空间时,操作简便. 但难以确定初始安排储备空间的大小,空间安排少了,简单产生溢出,空间安排多了,简单造成空间铺张.并且各个堆栈不能共享空间.（3 ）一般情形下,分别建立多个链接堆栈不考虑堆栈的溢出（仅受用户内存空间限制）,缺点是堆栈中各元素要通过指针链接,比次序储备结构多占用储备空间.2 T-lchild=NULL & T-rchild=NULL T-lchildT-rchild3 （由于图表显示限制,此题答案见指定教材 数据结构教程其次版 20XX年 4 月第 7 次印刷 第418 页 8-16题）4
22、 (1) 依据 =散列表中存入的元素数/ 散列表的长度,得到表的长度为18 ,因此,合适的散列函数应当为Hk=k MOD 17.(2) （由于图表显示限制,此题答案见指定教材数据结构教程其次版 20XX年 4 月第 7 次印刷 第428 页 9-15题）四、算法设计题SORTint A , int nint ,i, j, min, max, temp; i=1;whilei=n/2 min=i; max=i;forj=i+1;jn-i+1;j+ ifAjAmaxmax=j;/*确定某趟排序的最小值元素和最大值元素*/ ifmin.=itemp=Amin; Amin=Ai; Ai=temp;/*
23、交换 Amin与 Ai 的位置*/ ifmax.=n-i+1ifmax=itemp=Amin; Amin=An-i+1; An-i+1=temp; /*交换 Amin与 An-i+1的位置*/ elsetemp=Amax; Amax=An-i+1; An-i+1=temp;/*交换 Amax与 An-i+1的位置*/ i+;五、填空题1 break a/q2an-1=an-2 FUNC2a, n-13*a+i+i *a+i+N-i-14i.=0 n%10+ 05 ch-=30 ch-=266 *s+i t+7strlenp-1 pq8ch & 2494 &number10argv1,“ rb
24、” argv2,“ wb”六、简答题1 答：通常有以下三种方式：(1) 参数传递方式：函数调用时依据实参传递给形参内容的不同又分为值传递与的址传递两种.(2) 通过 return语句传递数据：被调用函数可以通过return语句将函数值传递给调用函数.(3) 利用全局变量传递数据.2 答：指针可以进行以下三种运算：(1) 指针加 / 减一个整数.表示以当前指针所指单元的的址为起点的后或前整数个数据的的址.(2) 指针减指针.表示两个的址之间的数据个数.（指针加指针为非法运算）(3) 比较.表示同类型的两个指针所指对象在的址位置上的关系.3 答：共用体具有以下三个特点：(1) 共用体变量的成员共用
25、一块储备空间,共用体变量所占用的字节数等于最长成员所占用的字节数.(2) 共用体不能在定义时进行初始化.(3) 共用体中的成员每次只能有一个起作用,当存入新成员时,原先的成员失效,其值被掩盖.4 答：使用文件的基本操作一般有以下五个步骤：(1) 在程序中包含头文件stdio.h(2) 定义文件指针.例如：FILE *fp;(3) 打开文件,使文件指针与磁盘中的实际储备的数据文件建立关联.例如：fp=fopen“ test.txt” ,“ r ” ;(4) 对文件进行读写操作.例如：freadf, 4, 2, fp;可编辑资料 - - - 欢迎下载精品_精品资料_(5) 文件使用完毕后,关闭文件
26、.例如：fclosefp;七、程序设计题#include main int a100, i, *p, k=0; p=a;fori=0; i100; i+scanf“ %d” , p+i; /*对数组进行数据输入*/fori=1; i*p+ik=i;fori=k; i99; i+/*删除最小值元素*/*p+i=*p+i+1;fori=0; i99; i+/*输出处理后数组各元素*/ printf“ %d” , *p+i;可编辑资料 - - - 欢迎下载精品_精品资料_printfn“” ;可编辑资料 - - - 欢迎下载精品_精品资料_八、程序设计题 函数的基本思想：从左至右次序扫描字符串s,逐
27、个找出单词,并记录单词的开头位置与单词的长度.如该单词的长度比已找到的单词更长, 就从左至右次序扫描字符串t .当在字符串t 中找到与在s 中找到的当前最长单词相匹配的单词时,记录单词的开头位置与单词的长度,并回到字符串s ,在其中找出下一个更长的单词.如此下去,只至字符串s 扫描终止,最终返回相应结果.#include #include char *maxwordchar *s, char *tchar res, *temp, chs, cht;int i, j, found, maxlen=0; while*s.=0 while*s=s+; /*过滤 s 中的空格*/fori=0; si.
28、= &s0i.= ; i+ /*确定 s 中单词*/ ifimaxlenchs=si;si=0;temp=t; found=0;while*temp.=0 &.foundwhile*temp=temp+; /*过滤 t 中的空格*/forj=0;tempj.= &tempj.=0 ;j+ /*确定 t 中单词*/ ifj=i可编辑资料 - - - 欢迎下载精品_精品资料_cht=tempj;tempj=0;ifstrcmps, temp=0 maxlen=i;res=s; found=1temp=cht;temp=&tempj;/*回到字符串t 的某一位置 */si=chs;s=&si; /*回到字符串s 的某一位置 */ifmaxlen=0return NULL; /*未找到最长公共单词,返回NULL */ elseresmaxlen+1=0;return res;/*找到最长公共单词,返回该单词*/可编辑资料 - - - 欢迎下载