2012年南京工业大学年828数据结构操作系统考研真题

南京工业大学2018 年硕士研究生入学考试初试试题（A 卷）科目代码：828 科目名称：数据结构与操作系统满分：150 分注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！第一部分：数据结构（共90 分）一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。

每小题2分，共30 分）1、通常所说的时间复杂度是指__________。

A.语句的频度B.算法的时间消耗C.渐进时间复杂度D.最坏的时间复杂度2、等概率条件下,在由 n 个结点构成的顺序表上做插入结点操作,需平均移动的结点数为__________。

A.nB.(n-1)/2C.n/2D.(n+1)/23、向具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__________。

A.O(1)B.O(n)1 / 10C.O(n2)D.O(log2n)4、从一个栈顶指针为 top 的链栈中删除一个结点时,用 x 保存被删除的结点,20 应执行列命令。

A.x=top; top=top->nextB.top=top->next;=top->dataB.C.x=top->data;D,x=top->data;top=top->next5、循环队列 SQ 队满的条件是__________。

A.SQ->rear=SQ->froat;B.(SQ->rear+1)%MAXLEN=SQ->froatC.SQ->rear+2=SQL->froatD.(SQ->rear+2)%MAXLEN=SQL->froat6、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作(称为输出受限的双端队列),若五个元素 a,b,c,d,e 依次进队,则不可能得到的出队顺序是__________。

2017年南京工业大学828数据结构与操作系统真题南京工业大学2017年硕士研究生入学考试初试试题（A卷）科目代码：828科目名称：数据结构与操作系统满分：150分注意:③本试题纸须随答题纸一起装入试题袋中交回！（可使用科学计算器）第一部分：数据结构（共90分）一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。

每小题2分，共30分）1.等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为。

A.nB.（n-1）/2C.n/2D.（n+1）/22.在单链表中，若要删除由指针q所指向结点的后结点，则执行的语句是。

A.p=q→next；p→next=q→next；delete p；B.p=q→next；q→next=p；delete p；C.p=q→next；q→next=p→next；delete p；D.q→next=q→next→next；q→next=q delete p；3.从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列命令。

A.x=top；top=top→ntxtB.top=top→ntxt；x=top→data；C.x=top→data；D.x=top→data；top=top→ntxt；4.在一个大小为M=50的顺序表示一个循环队列中，如果当前的尾指针rear=10，头指针front=20，则当前循环队列的元素个数为。

A.10B.11C.40D.415.下面说法不正确的是。

A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构表示D.广义表可以是一个多层次的结构6.一棵具有20个叶结点的完全二叉树最多有个结点。

A.38B.39C.40D.417.n个结点的线索二叉树上含有的线索数为。

A.2nB.n-1C.n+1D.n8.具有128个结点的完全二叉树的深度为。

A.6B.7C.8D.99.在结点数为n的最大堆中插入一个结点时，复杂度为。

目　录第一部分　历年考研真题汇编2006年南京工业大学计算机科学与技术学院828数据结构与操作系统考研真题第二部分　兄弟院校真题汇编2014年山东科技大学信息科学与工程学院830数据结构与操作系统考研真题2012年山东科技大学信息科学与工程学院838数据结构与操作系统考研真题2011年山东科技大学信息科学与工程学院827数据结构与操作系统考研真题2010年山东科技大学信息科学与工程学院827数据结构与操作系统考研真题第一部分　历年考研真题汇编2006年南京工业大学计算机科学与技术学院828数据结构与操作系统考研真题南京工业大学耍堕年硕士研究生入学考试试卷（A）〈本试题150分、3小时）考试科目：数据埃构与操作系统诸应学科、专业：计算机应用技术（注意：所有答题内容均余写在答鬼地上，在试卷上答题-独无效！）第-部分,数据结构（共90分）一、选择题（每小题2分，共20分）1＞数据的存储结构有廉序、健式、族引和四种疆条形式.丸线性 B.树形C,散列D一图监2、计算机体法必^具备输入、输出和尊5个特性。

A,易读性、稳定性和安全性B可行性、可移植性和可扩充性C,牖定性、有穷性和秘定性可行性、确定性和有穷性3、指出下列时间要杂度最耶的级别是________.A.对数阶Ofhfcn）B.线性阶&n）C,指数阶。

（2"）D,平方阶0（『）4、己知模式串P='ABAABC',其next函数值是*A.011213B.012223C0LH22D,0112215、数组A中，行下标i义卜列下总j从1-10.每个元素的长度为3个字节，从首地址SA开始连续存糖.慢数组核列存放时，元素A”的起始地址为=A.SA+141B.SA+1S0C SA+222 D.SA+226、设无向图的顼点个数为n,聊谖无向图最多有________条辿.A.n;B.tt（n+l）/2C n（n-L）/2D n-17、将序列（50.72.43.85,73.20,35,45.65.30）构造为二叉排序树，杏找元素35重进行________次元素间的比较.A.10B.7C.5D.4一』、除度《设根的层次为L）的完全二又树至少有一^结点.七X尹C i*-T一 D.2W—-—----------------———9、下述几种排序方法中，能完成对突数数绍进行榆定捧序的是_______•,A、归弁样序 B.堆排序 C.快速排虏 D.痿数择序I。

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

南京工业大学2015年硕士研究生入学考试初试试题（A卷）科目代码：828科目名称：数据结构与操作系统满分：150分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！第一部分：数据结构（共90分）一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。

每小题2分，共30分）1.下面算法的时间复杂度为。

int f（int n）{if（n==0||n==1）return1;else return n*f（n-1）}A.O（1）B.O（n）C.B.O（n2）D.O（log n）2.在一个长度为n的顺序存储的线性表中按照逐个比较的方法查找值为x的元素时（x在该线性表中），平均查找长度（即x与线性表中的元素平均比较次数，假定查找每个元素的概率都相等）为。

A.nB.n/2C.（n+1）/2D.（n-1）/23.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是。

A.p=q→next；p→netx=q→next；delete p；B.p=q→next；q→next=p；delete p；C.p=q→next；q→next=p→next；delete p；D.q→next=q→next→next；q→next=q；delete q→next；4.全元素按A，B，C，D顺序进入栈S，执行两次Pop（S，x）运算后，栈顶元素值是。

A.AB.BC.CD.D5.循环队列SQ队满的条件是。

A.SQ→rear==SQ→frontB.（SQ→rear+1）%MAXLEN==SQ→frontC.（SQ→rear+2）%MAXLEN==SQ→frontD.SQ→front==06.若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存两个字符，假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为。