重庆邮电大学2017年攻读硕士学位研究生入学考试(数据结构A)试题

重庆邮电大学2017年攻读硕士学位研究生入学考试试题
机密★启用前
重庆邮电大学
2017年攻读硕士学位研究生入学考试试题
科目名称：计算机网络
科目代码： 803
考生注意事项
1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考
单位和考生编号。

2、所有答案必须写在答题纸上，写在其他地方无效。

3、填（书）写必须使用0.5mm黑色签字笔。

4、考试结束，将答题纸和试题一并装入试卷袋中交回。

5、本试题满分150分，考试时间3小时。

注：所有答案必须写在答题纸上，试卷上作答无效！第1页（共6页）。

机密 启用前重庆邮电大学2021年攻读硕士学位研究生入学考试试题科目名称：数据结构（A）卷科目代码：802考生注意事项1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考单位和考生编号。

2、所有答案必须写在答题纸上，写在其他地方无效。

3、填（书）写必须使用黑色字迹钢笔、圆珠笔或签字笔。

4、考试结束，将答题纸和试题一并装入试卷袋中交回。

5、本试题满分150分，考试时间3小时。

一、选择题（本大题共15小题，每小题2分，共30分）1设N是描述问题规模的非负整数，下列程序段的时间复杂度是（）。

static int fun(int N) {if (N == 1) return 0;return 1 + fun(N/2);}A．O(log N) B. O(N) C. (N log N) D. O(N2)2一些随机产生的数采用线性链表存储，在下面这些排序方法中，（）的时间复杂度是最小的。

A．插入排序 B. 快速排序 C. 堆排序 D. 归并排序3一个栈的输入序列为a，b，c，d，e，则下列序列中不可能是栈的输出序列的是（）。

A．b c d a e B．e d a c b C．b c a d e D．a e d c b4实现一个队列需要（）个栈。

A．1 B. 2 C. 3 D. 45下面（）是一颗满二叉树的结点个数。

A.8B.13C.14D.156若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。

A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右的结点D.X的左子树中最右的结点7下列序列中，哪一个是堆（）？A.75, 65, 30, 15, 25, 45, 20, 10B.75, 65, 45, 10, 30, 25, 20, 15C.75, 45, 65, 30, 15, 25, 20, 15D.75, 45, 65, 10, 25, 30, 20, 158一棵Huffman树共有203个结点，对其Huffman编码，共能得到（）个不同的码字。

2017《数据结构》期末考试试题及答案2017《数据结构》期末考试试题及答案《数据结构》期末考试试题及答案1 (2)试题1答案 (7)《数据结构》期末考试试题及答案2 (9)试题2答案 (14)《数据结构》期末考试试题及答案3 (16)试题3答案 (21)《数据结构》期末考试试题及答案1⼀、单选题（每题 2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插⼊和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.⽤链接⽅式存储的队列，在进⾏插⼊运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪⼀个是⾮线性结构？( )A. 队列B. 栈C. 线性表D. ⼆叉树4.设有⼀个⼆维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占⼀个空间，问A[3][3](10)存放在什么位置？脚注(10)表⽰⽤10进制表⽰。

A．688 B．678 C．692 D．6965.树最适合⽤来表⽰( )。

A.有序数据元素B.⽆序数据元素C.元素之间具有分⽀层次关系的数据D.元素之间⽆联系的数据6.⼆叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在⼀维数组A[19]中，第⼀个元素放A[1]中，现进⾏⼆分查找，则查找A［3］的⽐较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的⽂件进⾏快速排序，所需要的辅助存储空间⼤致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进⾏散列存储时，若选⽤H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的⽆向图，该图⾄少应有( )条边才能确保是⼀个连通图。

机密★启用前重庆邮电大学2019年攻读硕士学位研究生入学考试试题科目名称：数据结构（A）科目代码：802考生注意事项1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考单位和考生编号。

2、所有答案必须写在答题纸上，写在其他地方无效。

3、填（书）写必须使用0.5mm黑色签字笔。

4、考试结束，将答题纸和试题一并装入试卷袋中交回。

5、本试题满分150分，考试时间3小时。

一、选择题（本大题共10小题，每小题2分，共20分）1．对于双向循环链表，每个结点有两个指针域next和prior，分别指向前驱和后继。

在p指针所指向的结点之后插入s指针所指结点的操作应为（）。

A.p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;2．由abc,3个结点可以构造出多少种不同的二叉树？（）A.2B.3C.4D.53.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。

A.BA+141B.BA+180C.BA+222D.BA+2254.一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是()。

A.231B.321C.312D.1235.下述编码中哪一个不是前缀码（）。

重庆邮电大学2017年攻读硕士学位研究生入学考试试题
机密★启用前
重庆邮电大学
2017年攻读硕士学位研究生入学考试试题
科目名称：概率论与线性代数（A卷）
科目代码： 814
考生注意事项
1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考
单位和考生编号。

2、所有答案必须写在答题纸上，写在其他地方无效。

3、填（书）写必须使用0.5mm黑色签字笔。

4、考试结束，将答题纸和试题一并装入试卷袋中交回。

5、本试题满分150分，考试时间3小时。

注：所有答案必须写在答题纸上，试卷上作答无效！第1页（共5页）。

精品文档，欢迎下载！重庆邮电大学2017 年攻读硕士学位研究生入学考试试题机密★启用前重庆邮电大学2017 年攻读硕士学位研究生入学考试试题科目名称：翻译硕士英语 (A 卷)科目代码：211考生注意事项1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考单位和考生编号。

2、所有答案必须写在答题纸上，写在其他地方无效。

3、填（书）写必须使用 0.5mm 黑色签字笔。

4、考试结束，将答题纸和试题一并装入试卷袋中交回。

5、本试题满分 150 分，考试时间 3 小时。

注：所有答案必须写在答题纸上，试卷上作答无效！第1 页 (共15 页）I.词汇语法部分（40 分）一、多项选择A.选择一项最佳答案将句子补充完整。

（共30 小题，每小题 0.5 分，共15 分）1.For the transaction to succeed, some means had to be found to thetrustee to comply with the terms of the trust.[A]compile [B]confront [C] compel [D]control2.For any Chinese or Asian, the successful launch of Shenzhou 5 is _ acause for jubilation.[A]doubtable [B] doubtless [C] doubtful [D] undoubted3.With the advance of the medical technology, some cancers are treated bytherapy nowadays.[A]radiant [B]radiance [C] radiation [D]radical4.Although 20 years passed, Mary still remembers some of that conversation.[A]pieces [B] chips [C] fragments [D] shatters5.His hands were white and small, his frame was , his voice was quietand his manners were refined.[A]briskly [B]delicate [C]fragile [D] breakable6.The technicians are working hard to the design of the new car tomake it more competitive in the overseas market.[A]find [B] modify [C] develop [D] make7.Temperatures will 38ºC over the weekend due to the heat wave,says the weather forecaster.[A]d rop down [B]fall down [C]soar into [D]soar up8.The schools themselves admit that not all children will be successful in the jobs,they are being trained.[A]in that [B] for that [C] in which [D] for which9.Those members requested that China undertake an appropriate commitment tothese practices.[A]cut off [B]eliminate [C]remove [D] struggle10.Generally speaking, this is not a usual exit. You should only use this door in a(n).[ A] emergence [B] emergency [C] urgency [D] accident11.The government has promised to do lies in its power to ease thehardships of the victims in the flood-[A]however [B]whichever [C] whatever [D] wherever12.The money withheld from the employee’s may be kept in thecompany’s checking account for a brief time until the payment is due.[A]bill [B] paycheck [C] paper [D] card13.The lecture which lasted about three hours was so that the audiencecouldn’t help yawning.[A]tedious [B] bored [C] clumsy [D] tired14.Whether or not we go to Europe for our holiday _ whether we can saveenough money to cover the cost.[A]depends on [B]relies on [C]builds on [D] takes on15.It remains a hot issue whether high school students should be encouraged toserious social issues like the causes of unemployment.[A]look after [B] look up [C]look into [D] look around16.The worsening economic conditions will lead to more crimes andmore victims.[A]a bsolutely [B] inevitably [C] certainly [D] undoubtedly17.Wines can be as dry, medium or sweet according to their sugarcontent.[A]d ivided [B] ranged [C] viewed [D] classified18.There’s absolutely no between the different work teams --- we don’tknow what others are doing.[A]agreement [B] coordination [C]understanding [D]discussion19.He was a really considerate friend --- always available to help at thehint of trouble.[A]sight [B]slight [C] slightest [D]signal20.The at the military academy is so rigid that most students canhardly bear it.[A]convention [B] confinement [C] principle [D] discipline21.Batista was keeping himself in power only by a mounting use of ,corruption and violence.[A]d epression [B] compression [C]confession [D]repression22.The coach was that Michael had recovered sufficiently from his kneeinjury and he was able to play in the semi-final next week.[A]relief [B] relieved [C] relaxed [D] reliable23.Critics believe that the control of television by mass advertising hasthe quality of the programs.[A]lessened [B] declined [C] affected [D] effected24.Now that spring is here, you can these fur coats till you need themagain next winter.[A]put over [B] put away [C] put off [D] put down25.Some people believe that since oil is scarce, the of the motorindustry is uncertain.[A]t erminal [B] benefit [C] fate [D] estimate26.The defense lawyer was questioning the old man who was one of theof the murder committed last month.[A]observers [B] witnesses [C] audiences [D] viewers27.Nancy was from the warehouse to the accounting office, which wasconsidered a promotion.[A]delivered [B] exchanged [C] transferred [D] transformed28.My grandmother has always taken a interest in my work, and I havean equal admiration for the stories of her time.[A]splendid [B] weighty [C] vague [D] keen29. quantities of water are being used nowadays with the rapiddevelopment of industry and agriculture.[A]Excessive [B] Extensive [C] Extreme [D] Exclusive30.Dr. Smith was always _ the poor and the sick, often providing them withfree medical care.[A]r eminded of [B]) concerned about [C]tended by [D] absorbed inB.选择与所给词意义相近的正确答案（共 10 小题，每小题 0.5 分，共 5 分）( ) 31. comprehensive A. accidental B. including muchC. delicateD. small( ) 32. conventional A. large B. at a conferenceC. outstandingD. ordinary( )33. enhance A . reject B. getC.improveD. free( ) 34. attribute A. admiration B. programC. diseaseD. quality( ) 35. recession A. parade B. amusementC. giving inD. business decline( ) 36.default A. jump B. fail to do something requiredC. do automaticallyD. seize( ) 37. degenerate A. give up B. improveC. stay the sameD. worsen( ) 38. implausible A. possible B. hard to believeC. imaginaryD. historical( ) 39. obsolete A. current B. difficult to believeC. out-of-dateD. not sold( ) 40. encounter A. meeting B. totalC. departureD. attack二、填空用括号内单词的正确形式填空（共 10 小题，每小题 0.5 分，共 5 分）41.The new law (power) the police to search private houses in anemergency.42.We shall be very glad to have your (present) at the annualmeeting.43.Rather quiet at first, he became very (talk) over his second glassof beer.44.She sued for divorce on the grounds of her husband’s alleged(conduct) with his secretary.45.She doesn’t like (door) sports even though she knows that it isgood for her health.46.A bar with (adjust) weights at each end is lifted for sport orexercise.47.She’s(fortune) in getting that good job, since the business isworse nowadays.48.Jane was so (apology) about forgetting her husband’s birthdayparty that it was almost embarrassing.49.There is great (like) now that interest rates will increase further.50.Before playing the new game, (familiar) yourself with the rules.三、改错（共10 小题，每小题 0.5 分，共 5 分）以下每个句子都有一个错误，请指出错误并改正。

2022年重庆邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、以下数据结构中，（）是非线性数据结构。

A.树B.字符串C.队D.栈4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

机密★启用前重庆邮电大学2018年攻读硕士学位研究生入学考试试题科目名称：数据结构科目代码： 802考生注意事项1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考单位和考生编号。

2、所有答案必须写在答题纸上，写在其他地方无效。

3、填（书）写必须使用0.5mm黑色签字笔。

4、考试结束，将答题纸和试题一并装入试卷袋中交回。

5、本试题满分150分，考试时间3小时。

一、选择题（本大题共15小题，每小题2分，共30分）1.下面程序段的时间复杂度是（）。

i ＝1；while（i＜＝n）i ＝i×3；A.O(n)B. O(nlog(n))C. O(log(n))D. O(log3n)2.在n个元素的顺序表中插入或删除一个元素，需要平均移动表中（）个元素。

A.(n)B. (n/2)C. (n2)D. (1)3.设循环队列中数组的下标范围是0, ..., m－1，其头指针front指向队首元素，rear指向队尾元素，则队列的长度为（）。

A．(rear－front＋1)％(m＋1) B．(rear－front＋m+1)％mC．rear－front D．rear－front＋14.设计一个十进制转换为八进制的算法，采用（）数据结构最佳。

A. 栈B. 队列C. 顺序结构线性表D. 链式结构线性表5.若某个栈的输入序列为1, 2, 3,…, n，输出序列的第一个元素为n，则第i个输出元素为（）。

A. iB. n-iC. n-i+1D. 哪个元素无所谓6.六个元素按6，5，4，3，2，1 的顺序进栈，下列哪个出栈序列是错误的（）。

A．5 4 3 6 1 2 B．4 5 3 1 2 6C．3 4 6 5 2 1 D．2 3 4 1 5 67.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）二叉树。

A．空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子8.高度为k的完全二叉树至少有（）个结点（空树高度为0）。

2017《数据结构》期末考试一试题及答案《数据结构》期末考试一试题及答案1..................................... .. (2)试题1答案............................................. ............................................... (7)《数据结构》期末考试一试题及答案2..................................... .. (9)试题2答案............................................. ............................................... (14)《数据结构》期末考试一试题及答案3..................................... (16)试题3答案............................................. ............................................... (21)第1页共23页《数据结构》期末考试一试题及答案 1一、单项选择题（每题2分，共20分）1. 栈和行列的共同特色是( )。

A.只同意在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点用链接方式储存的行列，在进行插入运算时().A.仅改正头指针B.头、尾指针都要改正C.仅改正尾指针D.头、尾指针可能都要改正以下数据结构中哪一个是非线性结构？()A.行列B.栈C.线性表D.二叉树4.设有一个二维数组A[m][n]，假定A[0][0]寄存地点在644(10)，A[2][2]寄存地点在676(10)，每个元素占一个空间，问A[3][3](10)寄存在什么地点？脚注(10)表示用10进制表示。