下载文档原格式
1、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。
编写一个算法完成下列功能：（1）．建立有向图G的邻接表存储结构；（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。
2、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
3、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}写出G的拓扑排序的结果。
G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V74、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。
void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点int i，top=0,tag[],longest=0;while(p || top>0){ while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下if(tag[top]==1) //当前结点的右分枝已遍历{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}//保留当前最长路径到l栈，记住最高栈顶指针，退栈}else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下}//while(p!=null||top>0)}//结束LongestPath5、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。
第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构 B．存储实现C．逻辑结构 D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。
A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树 B．字符串 C．队 D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
新疆维吾尔自治区考研计算机科学与技术题库精选在计算机科学与技术领域的快速发展下，越来越多的人选择考研来提升自己的学术水平和职业发展。
如果你有意向考取计算机科学与技术专业的研究生，那么新疆维吾尔自治区考研计算机科学与技术题库就是你必备的学习工具。
本篇文章将为大家精选一些新疆维吾尔自治区考研计算机科学与技术题库，帮助大家更好地准备考试。
一、数据结构与算法1. 以下哪个数据结构不是一种线性表结构？A. 数组B. 栈C. 队列D. 链表2. 以下排序算法中，时间复杂度最小的是？A. 冒泡排序B. 插入排序C. 选择排序D. 快速排序3. 希尔排序是插入排序的一种改进算法，它的基本思想是什么？A. 将数组分组进行插入排序B. 每次比较相隔一定距离的元素C. 每次比较相邻的元素交换位置D. 利用递归实现排序二、操作系统1. 下面哪个属于进程的特征？A. 可抢占性B. 共享性C. 计算性D. 不确定性2. 页面置换算法主要用于解决什么问题？A. 外部碎片B. 内部碎片C. 死锁D. 缓存污染3. 在Linux中，用于调度进程的默认调度算法是什么？A. 先来先服务（FCFS）B. 最短作业优先（SJF）C. 时间片轮转（RR）D. 优先级调度三、数据库系统1. 下列哪个不属于数据库的基本操作之一？A. 增加B. 删除C. 修改D. 查找2. 事务的四个特性是什么？A. 原子性、一致性、隔离性、持久性B. 原子性、一致性、隔离性、可靠性C. 一致性、隔离性、持久性、可靠性D. 原子性、一致性、可靠性、可靠性3. 下面哪个是数据库表的属性？A. 元组B. 字段C. 键D. 主键通过以上题目的例示，我们可以看出新疆维吾尔自治区考研计算机科学与技术题库的题目类型主要涵盖了数据结构与算法、操作系统以及数据库系统等多个方面。
针对这些题目，我们需要系统地学习相关知识，并进行深入理解和掌握。
为了更好地应对考试，有几点建议如下：首先，建议大家制定合理的学习计划。
第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构 B．存储实现C．逻辑结构 D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。
A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树 B．字符串 C．队 D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
1、#define maxsize 栈空间容量void InOutS(int s[maxsize])//s是元素为整数的栈，本算法进行入栈和退栈操作。
{int top=0; //top为栈顶指针，定义top=0时为栈空。
for(i=1; i<=n; i++) //n个整数序列作处理。
{scanf(“%d”,&x); //从键盘读入整数序列。
if(x!=-1) // 读入的整数不等于-1时入栈。
if(top==maxsize-1){printf(“栈满\n”);exit(0);}else s[++top]=x; //x入栈。
else //读入的整数等于-1时退栈。
{if(top==0){printf(“栈空\n”);exit(0);}else printf(“出栈元素是%d\n”,s[top--])；}}}//算法结2、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。
若非二叉排序树，则置flag为false。
#define true 1#define false 0typedef struct node{datatype data; struct node *llink,*rlink;} *BTree;void JudgeBST（BTree t,int flag）// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。
{ if（t!=null && flag）{ Judgebst（t->llink,flag）；// 中序遍历左子树if（pre==null）pre=t；// 中序遍历的第一个结点不必判断else if（pre->data<t->data）pre=t；//前驱指针指向当前结点else{flag=flase；} //不是完全二叉树Judgebst （t->rlink,flag）；// 中序遍历右子树}//JudgeBST算法结束3、假设以I和O分别表示入栈和出栈操作。
绪论一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：集合＿、线性结构＿、树型结构＿、图状结构＿。
2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：顺序存储＿、链式存储＿、索引存储＿、散列存储＿。
二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（B ）。
A、正确性B、有穷性C、确定性D、可行性2、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（A）。
A、正确性B、有穷性C、确定性D、可行性3、算法原则上都是能够有机器或人所完成的。
整个算法好象是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作，这是算法的（D）A、正确性B、有穷性C、确定性D、可行性三、简单题1、什么是数据结构？什么是算法？两者有什么关系？什么是数据结构？数据结构是按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。
什么是算法？广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”两者有什么关系？算法与数据结构关系密切。
选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。
2、什么是复杂度和空间复杂度？时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。
3、数据的逻辑结构分几种？存储结构又有哪几种？数据的逻辑结构：结构定义中的“关系”，描述的是数据元素之间的逻辑关系；包括线性结构（线性表、栈、队、串、数组）和非线性结构（图形结构、树形结构）；数据的存储结构（物理结构）：数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系德表示。
有顺序存贮（向量存贮）、链式存贮、索引存贮、散列存贮。
线性表1、一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第5 个元素的地址是( B)。
数据结构与算法题库（附参考答案）一、单选题（共86题，每题1分，共86分）1.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、O(NlogN)B、O(N)C、O(N2)D、O(logN)正确答案：C2.一棵有 1001 个结点的完全二叉树，其叶子结点数为▁▁▁▁▁ 。
A、254B、250C、501D、500正确答案：C3.对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是：A、(N−1)2B、NC、N2D、N−1正确答案：C4.在有n（>1）个元素的最大堆（大根堆）中，最小元的数组下标可以是：A、⌊n/2⌋−1B、⌊n/2⌋+2C、1D、⌊n/2⌋正确答案：B5.一棵非空二叉树，若先序遍历与中序遍历的序列相同，则该二叉树▁▁▁▁▁ 。
A、所有结点均无左孩子B、所有结点均无右孩子C、只有一个叶子结点D、为任意二叉树正确答案：A6.度量结果集相关性时，如果准确率很高而召回率很低，则说明：A、大部分检索出的文件都是相关的，但还有很多相关文件没有被检索出来B、大部分相关文件被检索到，但基准数据集不够大C、大部分检索出的文件都是相关的，但基准数据集不够大D、大部分相关文件被检索到，但很多不相关的文件也在检索结果里正确答案：A7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用哪种存储方式最节省运算时间？A、单循环链表B、带头结点的双循环链表C、单链表D、双链表正确答案：B8.设数组 S[ ]={93, 946, 372, 9, 146, 151, 301, 485, 236, 327, 43, 892}，采用最低位优先（LSD）基数排序将 S 排列成升序序列。
第1 趟分配、收集后，元素 372 之前、之后紧邻的元素分别是：A、43，892B、236，301C、301，892D、485，301正确答案：C9.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、O(NlogN)B、O(N2)C、O(N)D、O(logN)正确答案：B10.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都会停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、O(NlogN)B、O(N)C、O(logN)D、O(N2)正确答案：A11.如果AVL树的深度为6（空树的深度定义为−1），则此树最少有多少个结点？A、12B、20C、33D、64正确答案：C12.已知指针ha和hb分别是两个单链表的头指针，下列算法将这两个链表首尾相连在一起，并形成一个循环链表（即ha的最后一个结点链接hb 的第一个结点，hb的最后一个结点指向ha），返回ha作为该循环链表的头指针。
1、链式存储的存储结构所占存储空间（ A ）。
A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B）只有一部分，存放结点值
C）只有一部分，存储表示结点间关系的指针
D）分两部分，一部分存放结点值，另一部分存放结点所占单元数
2、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。
A）顺序表示法 B）单字符为结点的单链表表示法
C）等量分块表示法 D）不等量分块表示法
3、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。
A）13 B）33 C）18 D）40
4、广义表head(((a,b),(c,d)))的运算结果为（ A ）。
A）(a,b) B）(c,d)
C）空表 D）（（a,b）,(c,d)）
5、在数据结构中，从逻辑上可以把数据结构分为（ C ）。
A）动态结构和静态结构 B）紧凑结构和非紧凑结构
C）线性结构和非线性结构 D）内部结构和外部结构
6、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。
A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]
C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]
7、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。
A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;
C）p->next=s->next; s->next=p D）p->next=s; s->next=q;
8、n个顶点的图的最小生成树必定（ D ），是不正确的描述。
A）不唯一 B）权的总和唯一
C）不含回路 D）有n条边
9、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。
A）loc(A1)+i*c B）loc(A1)+(i-1)*c
C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c
10、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。
A）3 B）4 C）5 D）1
11、（ C ）在进行插入操作时，常产生假溢出现象。
A）顺序栈 B）循环队列
C）顺序队列 D）链队列
12、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。
A）front=front->next; B） rear=rear->next;
C） rear=front->next; D） front=rear->next ;
13、（ C ）在进行插入操作时，常产生假溢出现象。
A）顺序栈 B）循环队列
C）顺序队列 D）链队列
14、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。
A）4 B）5
C）6 D）7
15、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。
A）13 B）33 C）18 D）40。
