02笔试题-数据结构部分.doc

数据结构1.采用折半搜索算法长度为n的有序表时，元素的平均搜索长度为（）A)O(n2) B)O(nlog2n) C)O(log2n) D)O(n)2.下面程序的时间复杂度为（）for(int i=0;im;i+)for(int j=0;jn;j+)aij = i * j; A)O(m2); B)O(n2); C)O(m*n); D)O(m+n);3.下列叙述中，正确的是（）A)线性表中的个元素在存储空间中的位置必须是连续的B)线性表中的表头元素一定存储在其他元素的前面C)线性表中的个元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面D)线性表中的个元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的4.已知二叉树后序遍历序列是edcfba，中序遍历序列deacbf，它的前序遍历序列是（）;5.如果进栈序列为 e1,e2,e3,e4 ，则可能的出栈序列是（）;6.对长度为n的字符串进行字符定位运算的时间复杂度为（）;A)O(1) B)O(根号n) C)O(nlog2n) D)O(n)7.n个顶点的连通图中边得条数至少为（）8.合并两个已经排好序的长度为n的Array,最坏情况下需要比较多少次（）A)2n B)2n-1 C)2n+1 D)n29.深度为5的满二叉树中，叶子结点的个数为（）A)32 B)31 C)16 D)1510.冒泡排序算法和快速排序算法的时间复杂度分别是什么？11.请简述数组和链表数据结构的特点及应用的场合？12.下列哪些数据结构最适合医疗仪器设备中的大型数据量的插入，查找（）A)数组 B)哈希表 C)红黑树/二叉平衡树 D)链表13.下列哪些排序算法的平均时间复杂度是O(nlog2n)（），哪些是稳定的排序（）A)冒泡排序 B)希尔排序 C)快速排序 D)插入排序 E)堆排序14.下列哪些说法是正确的：（）A)二分查找法在一个长度为1000的有序整数数组查找一个整数，比较的次数不超过100次B)在二叉树中查找元素的时间复杂度为O(log2n)；C)对单向链表，可以使用冒泡排序；D)对双向链表，可以使用快速排序；15.已知某二叉树的后序遍历是DFBEGCA，中序遍历的顺序是DBFACEG，其前序遍历顺序是_16.下列代码将两个有序链表结合为一个，链表中的元素的排列顺序为从小到大。请补充其中的空缺。struct nodestruct node *pnext;int val;struct node* splice(struct node* plhs,struct node* prsh)if(_)return prhs?prhs:plhs;struct node* phead,*plast;if(_)phead = plast = prhs;plhs = plhs-pnext;elsephead = plast = plhs;prhs = prhs-pnext;while(_)if(plhs-val val)plast-pnext = plhs;plast = plhs;plhs = plhs-pnext;elseplast-pnext = prhs;plast = prhs;prhs = prhs-pnext;plast-pnest = _;return _;17. 比较哈希表和平衡二叉树的特点，他们分别用在哪些场合.18.一个栈的入栈序列是 A,B,C,D,E 则栈的不可能的输出序列是（）A) EDCBA B)DECBA C)DCEAB D)ABCDE19.在排序的方法中，关键码比较次数与记录地初始排列无关的是（）A) Shell B)归并排序 C)直接排序 D)选择排序 20.以下反向遍历array数组的方法有什么错误？vector array;array.push_back(1);array.push_back(2);array.push_back(3);for(vector:size_type i=array.size()-1;i=0;-i)cout arrayi next48.设单链表中节点的结构为： typedef struct nodeElemtype data; /数据struct node* Link; /节点后继指针Listnode;（1）已知指针p所指节点不是尾节点，若在*p之后插入节点*s，则应执行下列哪一个操作？A)s-link=p;p-link=s; B) s-link=p-link;p-link=s;C)s-link=p-link;p=s; D) p-link=s;s-link=p; (2) 非空的循环单链表 first 的尾节点（由p所指向）满足：A) p-link=NULL; B) p=NULL;C) p-link=first; D) p=first;49.如何证明一个表是循环链表？52.如果一棵二叉树节点的前序序列是 A、B、C，后序序列是C、B、A，则该二叉树节点的中序序列是什么？ A) 必为ABC B) 必为ACB C) 必为BCA D) 不能确定 53.什么是平衡二叉树？54.下面的程序是一快速排序问题，请填空。 #include #include void improveqsort(int *list,int m,int n)int k,t,i,j; /*for (i=0;i10;i+)printf(%3d,listi);*/if(mn)i=m;j=n+1;k=listm;while(ij)for(i=i+1,i=k)break;for(j=j-1,jm,j-)if(listj=k)break;if(ij)t=listi;listi=listj;listj=t;t=listm;listm=listj;listj=t;improveqsort( );improveqsort( );main()int list10;int n=9, m=0,i;printf(input 10 number:);for(i=0;i10;i+)scanf(%d,&listi);printf(n);improveqsort(list,m,n);for(i=0;i10;i+)printf(%5d,listi);printf(n);55.以下哪种排序属于稳定排序？ A) 归并排序 B) 快速排序 C) 希尔排序 D) 堆排序56.用二分法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较多少次？ A) 5 B) 2 C) 4 D) 1 57.下面那种排序法对 1234567 最快？ A) quick sort B) bubble sort C) merge sort58.解释一下什么是哈夫曼编码问题？59.假设执行语句Q的时间是O（1），则执行下列程序段的时间为（）for(int i = 1;i = n;i+)for(int j = i; j next=p;q-next =s;I. 在一个单链表中，若删除p所指节点的后续结点，则执行p=p-next;p-next=p-next-nextJ. 使用链表，可随机访问链表中的任何一个元素100.调用printf函数可以分解为九个过程，请写出他们的排列顺序_.A.call指令 B.EBP出栈 C.函数参数压栈 D.收回局部变量空间 E.EBP压栈F.在栈上保留局部变量 G.函数参数出栈 H.ret指令 I.打印输出字符串102.在以下几种数据结构中，在执行数量相当的查找，删除和插入操作时，综合性能最好的数据结构是：A. 双向链表 B. 分块链表 C. 穿线二叉树 D. 堆103. 广告系统为了做地理位置定向，将IPV4分割为627672个区间，并标识了地理位置信息，区间之间无重叠，用二分查找将IP地址映射到地理位置信息，请问在最坏的情况下，需要查找多少步？A17 B18 C19 D20104.以入栈顺序作为输入，出栈作为输出，并以I代表入栈，O代表出栈，现将1,2,3,4顺序入栈，则栈操作序列IIIIOOOO后，输出4321；与输出1234相对应的栈操作序列为IOIOIOIO.则若想得到输出为2314，则栈操作序列应为_.无法由栈操作序列而得到的输出有_。105. 设一组初始记录关键字序列为（20,18,22,16,30,19），则根据这些初始关键字序列建成的初始堆为_.106.线性有序表（a1,a2,a3,.a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与K相等的元素，在查找不成功的情况下，最多需要检索_次。编程1 单链表1：编程实现一个单链表的建立。2：编程实现一个单链表的侧长。3：编程实现一个单链表的打印。4：编程实现一个单链表删除节点。5：编程实现单链表的插入。6：编程实现单链表的逆置。2 双链表1：编程实现双链表的建立。2：编程实现双链表的侧长。3：编程实现双链表的打印。4：编程实现双链表删除节点。5：编程实现双链表的插入。1：编程实现队列的入队。2：编程实现队列的出队。3：编程实现队列的侧长。4：编程实现队列的打印。1. 一个学生的信息：姓名，学号，性别，年龄等信息，用一个链表，把这些学生信息连在一起，给出一个age，在这些链表中删除学生年龄等于age的学生信息。2. 请用C或 C+ 写出一个冒泡排序程序，要求输入10个整数，输出排序结果。3. 请用C或 C+ 写出一个shell排序程序，要求输入10个整数，输出排序结果。4. 链表struct studentint m_Num; /学号double m_dScore; /分数struct student* m_pNext; /下一个1).构造一个有20名学生的单向链表。按顺序每名学生的分数值为，1,2,3,5,8,13.2).求出他们的平均分。5. 请实现一个快速排序的算法。仅考虑排序的对象为整数的情况。6. 计算a的n次方是许多加密算法的基本操作，蛮力计算方法的时间复杂度是O(n)，请设计一个时间复杂度小于O(n)的算法，(假设计算结果可以使用long型存储)7.给定一个数组an，我们希望构造数组bn，其中 bi = a0*a1.an-1/ai.在构造过程不允许使用除法。1.要求O(1)空间复杂度和O(n)时间复杂度。2.除遍历计数器与anbn外，不可使用新的变量（包括栈临时变量，堆空间和全局静态变量等）；8.给定一个如下输入格式的字符串，（1，（2,3），（4，（5,6），7）括号内的元素可以是数字，也可以是另一个括号。请实现一个算法消除嵌套的括号，比如把上面的表达式变成：（1,2,3,4,5,6,7），如果表达式有误请报错。9.相似度计算用于衡量对象之间的相似程度，在数据挖掘，自然语言处理中是一个基础性计算。在广告检索服务中往往也会判断网民检索Query和广告Adword的主题相似度。假设Query或者Adword的主题属性定义为一个长度为10000的浮点数组Pr10000（称之为主题概率数组），其中Pri表示Query或者Adword属于主题ID为i的概率，而Query和Adword 的相似度简化定义为两者主题概率数组的内积：即sim(Query,Adword) = sum(QueryPri*AdwordPri) (0=i=10000)。在实际应用场景中，由于大多数主题概率都为0，所以主题概率数组往往比较稀疏，在实现时会以一个紧凑型数组topic_info_t的方式保存，其中100=数组大小=1000,并按照topic_id递增排列，0=topic_id10000,0topic_pr=5000）个Adwords的topic_info_t数组，现要求出Query与Adwords的相似度最大值。即max(sim(Query,Adwordi)(0=iN).float max_sim(const vector&query_topic_info,const vectoradwords_topic_info,int adwords_number);编写代码求时间复杂度最低的算法，并给出时间复杂度分析。10. 给一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么b是a的兄弟单词，比如单词army和mary互为兄弟单词。现在要给出一种解决方案，对于用户输入的单词，根据给定的字典找出输入单词有哪些兄弟单词。请具体说明数据结构和查询流程，要求时间和空间效率尽可能的高？11. 系统中维护了若干数据项，我们对数据项的分类可以分为三级，首先我们按照一级分类方法将数据项分为A，B，C若干类别，每一个级分类方法产生的类别又可以按照二级分类方法分为a,b,c若干子类别，同样，二级分类方法产生的类别又可按照三级分类方法分为i,ii,iii若干子类别，每个三级分类方法产生的子类别中的数据项从1开始的编号。我们需要对每个数据项输出日志，日志的形式是key-value。写入日志的时候，用户提供三级类别名称，数据项编号和日志的key，共五个key值，例如write(A,a,i,1,key1)，获取日志的时候，用户提供三级类别名称，数据项编号，共四个key值，返回对应的所有key-value，例如get_log(A,a,i,1)，请描述一种数据结构来存储这些日志，并计算出写入日志和读出日志的时间复杂度？12.链表struct student int m_Num;/学号double m_dScore;/分数struct student *m_pNext;/下一个;1）构造一个有20名学生的单向链表。按顺序每名学生的分数值为1,1,2,3,5,8,132）求出他们的平均分13.冒泡排序（写出具体算法）：答题需注意程序的有效性，可行性，健壮性并体现严格，规范的过程。14.单链表反序（写出具体算法）：答题需注意程序的有效性，可行性，健壮性并体现严格，规范的过程。15.请写一个函数，功能是把一段字符串倒序：答题需注意程序的有效性，可行性，健壮性并体现严格，规范的过程。16.设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度为O（N）,空间复杂度为O（1）。17.一个单向链表，不知道头结点，一个指针指向其中一个节点，问如何删除这个指针指向的结点.18.编程得到以下算式的结果（要求计算的效率最高） 算式：1-2+3-4+5-6.N19.请写出一个程序，把一段字符串里面的某个字符（可能出现几次）过滤掉，比如“abcdefg”过滤掉e变成“abcdfg”。要求算法复杂度O(n)，空间复杂度O(1)(10)。20.编写一个按单词反转字符串的函数，如给定输入 here is 后变成 is here21.列出你知道的排序算法，并使用其中的任意一种排序算法实现int *sort(int array,int length),array是一个待排整形数组，length是数组长度，将排序结果以整型指针的形式输出。22. 编写一个函数，计算两个正整数的最小公倍数，要求用辗转相除法。23已知两个链表List1和List2，均为增序，请把他们合并成一个链表，要求仍为增序，请用递归实现。24.编程求10000以内的素数，要求对算法进行适当优化。25.（八皇后问题）在一个8*8的国际象棋棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列或同一斜线上。请编程求出所有可行的摆法，要求用回溯法写出程序。26.给定一个单链表和一个整数K，要求每隔K个元素翻转链表：struct nodeint key;struct node * next;typedef node *List;实现该函数：int *kReverse(List *Head,int k)比如：原始链表为：1-2-3-4-5-6k=2翻转为:2-1-4-3-6-5k=3翻转为:3-2-1-6-5-4k=4翻转为:4-3-2-1-5-627.对于一个m*n的int矩阵，其每行自左向右是升序排列的，其每列自上向下是升序排列的，现需要在其中查找整数elem，找到时返回elem所在位置。请1）先写出思路；2）自行定义函数接口然后编程实现，编程语言不限。28.下面程序段的时间复杂度为（）for(int i=0;im;i+)for(int j =0 ;j2-3-4-5）,现有指针P指向节点3，现在要删除节点3，把链表L变成（1-2-4-5）30. 已知一颗二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这颗二叉树.31.给定一个没有重复数据的整数数组，找出其中所有两个数相加之和等于2013的整数对，并且打印出来。（请写出你的思路，然后用代码实现出来）32. 已知两个集合A5，2，7，4，3，9，9 B5，3，1，9，2，6，2，写一段代码顺序打印出这两个集合中重复的元素。尝试使你的代码时间复杂度最优，请在代码之前写出你的思路。33. 已知字母顺序是d，g，c，f，b，e，a 请对输入的一组字符串input3=“dca”，“dfa”，“cgd”,按照字母顺序进行排序并打印，本例的输出为：1：dca2：dfa3：cgd如何检测上述代码是达到质量标准的？34.create a function for string padStart(String string,int minlength,char padChar);return a string,of length at least minlength,consisting of string prepended with as many copies of padChar as are necessary to reachthat length.for example :padStart (“7”,3,0)returns “007”padStart (“2010”,3,0)returns “2010”35.有一个数组，里面由若干整数组成，除了一个整数外，其他都出现两次，如何快速找到这个整数。例如：【1，2,1,3,4,4,3】，输出应为2.36.给定两个有序单链表，求这两个单链表的交集链表，并维持交集依然有序。请给出代码实现，自己定义数据结构。如有链表：1-2-4-8和2-3-4-5交集为2-4，函数头为Node *intersect(Node *list_a,Node *list_b);36. 请编写函数实现整型数组的循环右移；void rightshift(int *arr,int size,int k);其中k为右移量。形如1,2,3,4 要求向右循环移位两位，结果是：3,4,1,2.37.写一个函数，找出一个字符串中出现频率最高和最低的单词（不区分大小写）。假定字符串由英文单词组成。以0结束，各单词之间由英文标点,或.或空格区分。38. 近来有人生成发明了一类神奇的直角三角形，其每一条边的长度都是互不相等的Fibonacci数，聪明的你能找到这样的三角形吗？如果能，请写出符合 条件的三个数值，如果不能，请写出分析过程，Fibonacci数：满足：f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2).39.计算a的n次方是许多加密算法的基本操作，蛮力计算方法的复杂度是O（n），请设计一个时间复杂度小于O（n）的算法，（假设计算结果可以使用long型存储）。40.不调用库函数split_ext,该函数作用是从WINDOWS格式路径中提取文件的后缀名，函数原型：char*split_ext(const char*pszPath