数据结构试题

数据结构考题~

答案保证正确，
1、在双向循环链表的p所指结点之后插入s所指结点的操作是（D）。
Ap->right=s;s->left=p;p->right->left=s;s->right=p->right;
Bp->right=s;p->right->left=s;s->left=p;s->right=p->right;
Cs->left=p;s->right=p->right;p->right=s;p->right->left=s;
Ds->left=p;s->right=p->right;p->right->left=s;p->right=s;


2、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（C）。
A80
B100
C240
D270



3、在一个单链表中，若删除p所指结点的后续结点，则执行（A）。
Ap->next=p->next->next;
Bp=p->next;p->next=p->next->next;
Cp->next=p->next;
Dp=p->next->next；


4、数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是（B）有限集合，R是D上的关系有限集合。
A算法
B数据元素
C数据操作
D数据对象



5、不带头结点的单链表head为空的判定条件是（A）。
Ahead= =NULL
Bhead->next= =NULL
Chead->next= =head
Dhead!=NULL

原序列有十个数: 10 18 4 3 6 12 1 9 18 8[ 以10为基准,处理全部十个数 ] 10与8 互换,得到: 8 18 4 3 6 12 1 9 18 10 10与18互换,得到: 8 10 4 3 6 12 1 9 18 18 10与9 互换,得到: 8 9 4 3 6 12 1 10 18 18 10与12互换,得到: 8 9 4 3 6 10 1 12 18 18 10与1 互换,得到: 8 9 4 3 6 1 10 12 18 18第1趟排序的结果: 8 9 4 3 6 1 10 12 18 18[ 以8为基准,处理 8 9 4 3 6 1 ] 8与1互换,得到: 1 9 4 3 6 8 10 12 18 18 8与9互换,得到: 1 8 4 3 6 9 10 12 18 18 8与6互换,得到: 1 6 4 3 8 9 10 12 18 18第2趟排序的结果: 1 6 4 3 8 9 10 12 18 18[ 以1为基准,处理 1 6 4 3 ] 1比右边的数字都小,不用交换第3趟排序的结果: 1 6 4 3 8 9 10 12 18 18[ 以6为基准,处理 6 4 3 ] 6与3互换,得到: 1 3 4 6 8 9 10 12 18 18第4趟排序的结果: 1 3 4 6 8 9 10 12 18 18[ 以3为基准,处理 3 4 ] 3比4小,不用交换第5趟排序的结果: 1 3 4 6 8 9 10 12 18 18[ 以12为基准,处理 12 18 18 ] 12比右边的数字都小,不用交换第6趟排序的结果: 1 3 4 6 8 9 10 12 18 18[ 以18为基准,处理 18 18 ] 18与18不用交换第7趟排序的结果: 1 3 4 6 8 9 10 12 18 18这就是最后的排序结果.// C语言测试程序#include #define MAXSIZE 10000 /* 用于要排序数组个数最大值，可根据需要修改 */typedef struct{int r[MAXSIZE+1];/* 用于存储要排序数组，r[0]用作哨兵或临时变量 */int length;/* 用于记录顺序表的长度 */}SqList;int g_count;/* 交换L中数组r的下标为i和j的值 */void swapData(SqList *L,int i,int j){int temp=L->r[i];L->r[i]=L->r[j];L->r[j]=temp;}void printData(SqList L){int i;printf("(%d) ",g_count);for(i=1;ir[low]; /* 用子表的第一个记录作枢轴记录 */while(lowr[high]>=pivotkey)high--; swapData(L,low,high);/* 将比枢轴记录小的记录交换到低端 */ while(lowr[low]r[low..high]作快速排序 */void QSort(SqList *L,int low,int high){int pivot;if(lowr[low..high]一分为二，算出枢轴值pivot */ ////////测试 printData(*L); //////// QSort(L,low,pivot-1);/* 对低子表递归排序 */ QSort(L,pivot+1,high);/* 对高子表递归排序 */}}/* 对顺序表L作快速排序 */void QuickSort(SqList *L){QSort(L,1,L->length);}int main(){ int d[]={10,18,4,3,6,12,1,9,18,8}; int N; int i; SqList LT; N=sizeof(d)/sizeof(int); for(i=0;i<N;i++) { LT.r[i+1]=d[i]; } LT.length=N; printf("快速排序:
"); printData(LT); QuickSort(<); return 0;}

一.判断题
（ ）1.某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。
正确。第0个元素地址为100，则第i个元素地址为100+4*i，将12代入得148。

（ ）2.在任何一种线性链表上都无法进行随机访问。
错误。比如只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。

（ ）3.顺序栈是一种规定了元素进栈顺序的栈。
错误。按存储结构来分，堆栈分为顺序栈和链栈，其中栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表，却并没有规定元素进栈顺序。

（ ）4.循环列表中每一个元素都有后继。
正确。注意，这里可能有笔误，应写为“循环链表”而非“循环列表”。

（ ）5.删除一个二叉树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。
错误。

二.填空题。
6.下面程序的时间复杂度为___________。
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++ )
S+=i
法则1：for循环：一个for循环的运行时间至多是该for循环内语句（包含测试）的运行时间乘以迭代的次数。
法则2：嵌套循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。
对于此处嵌套的for循环，根据以上法则，时间复杂度为O(m*n)。

7.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数是____________。
从第i个元素（原来的）到第n个元素，每个元素后移一位，一共需要n+1-i次。

8.在一个具有n个结点的有序单链表中插入一个新结点，并让插入后的单链表仍然有序，则该操作的时间复杂性数量级为______。
找到节点位置，O(n)；单链表插入操作，O(n)；总的时间复杂度为O(n+n)=O(n)。

9.若用s[1]～s[n]作为两个顺序栈的共同存储空间，左右两个栈的栈顶分别为t1和t2，则判断某个栈是否可以插入新元素的条件是_________________。
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
此处判断某个栈是否可以插入新元素的条件是&t1!=&t2

10.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有____________个结点。
将一个森林转换为二叉树的具体方法是：① 将森林中的每棵树变为二叉树；② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
个人认为此处可以填3个答案，n1-1或者n2-1或者n3-1。

11.在带权值有向图的邻接矩阵中，第i行上非零元素的个数等于_______________。
当节点Vi与某节点Vj相邻接,则A(i,j)取非0值。

12.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____________。
散列（Hash）查找。

一.判断题
（ ）1.某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。
正确。第0个元素地址为100，则第i个元素地址为100+4*i，将12代入得148。

（ ）2.在任何一种线性链表上都无法进行随机访问。
错误。比如只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。

（ ）3.顺序栈是一种规定了元素进栈顺序的栈。
错误。按存储结构来分，堆栈分为顺序栈和链栈，其中栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表，却并没有规定元素进栈顺序。

（ ）4.循环列表中每一个元素都有后继。
正确。注意，这里可能有笔误，应写为“循环链表”而非“循环列表”。

（ ）5.删除一个二叉树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。
错误。

二.填空题。
6.下面程序的时间复杂度为___________。
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++ )
S+=i
法则1：for循环：一个for循环的运行时间至多是该for循环内语句（包含测试）的运行时间乘以迭代的次数。
法则2：嵌套循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。
对于此处嵌套的for循环，根据以上法则，时间复杂度为O(m*n)。

7.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数是____________。
从第i个元素（原来的）到第n个元素，每个元素后移一位，一共需要n+1-i次。

8.在一个具有n个结点的有序单链表中插入一个新结点，并让插入后的单链表仍然有序，则该操作的时间复杂性数量级为______。
找到节点位置，O(n)；单链表插入操作，O(n)；总的时间复杂度为O(n+n)=O(n)。

9.若用s[1]～s[n]作为两个顺序栈的共同存储空间，左右两个栈的栈顶分别为t1和t2，则判断某个栈是否可以插入新元素的条件是_________________。
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
此处判断某个栈是否可以插入新元素的条件是&t1!=&t2

10.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有____________个结点。
将一个森林转换为二叉树的具体方法是：① 将森林中的每棵树变为二叉树；② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
个人认为此处可以填3个答案，n1-1或者n2-1或者n3-1。

11.在带权值有向图的邻接矩阵中，第i行上非零元素的个数等于_______________。
当节点Vi与某节点Vj相邻接,则A(i,j)取非0值。

12.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____________。 纠正错误

判断题第一题是错的，因为不知道是按照行排列还是按照列排列
判断题第一题是对的，因为线性链表如果是单项的只能从头访问，要是双向的也只能从头或者从尾访问，但是无论如何也不能随机访问。
散列（Hash）查找。

纠正错误

判断题第一题是错的，因为不知道是按照行排列还是按照列排列
判断题第一题是对的，因为线性链表如果是单项的只能从头访问，要是双向的也只能从头或者从尾访问，但是无论如何也不能随机访问。

看明白了，可乐说的很详细了

按时的

---

准格尔旗17770811570： 《数据结构》在线作业二、判断题(共 20 道试题,共 40 分.)V 1. 线性表中的数据元素必须具有相同的特性,即属于同一个数据对象,这种线性表称为同质... - ？
犹些多它：[答案] 1. B 2. A (循环队列一般是指顺序存储) 3.B(只有根节点无前驱) 4.A (是顺序存取) 5.A(指向头结点) 6.A(5出栈后,1在2的下面,不可能先出) 7. B(看书上公式) 8. A (链式存储时不一定相同) 9. B 10.A 11. A 12. B 13 A 14.(是不等长的...

准格尔旗17770811570： 数据结构试题一道已知如下程序段FOR i:= n DOWNTO 1 DO {语句1}BEGIN x:=x+1; {语句2}FOR j:=n DOWNTO i DO {语句3} y:=y+1; {语句4}END;语句1执... - ？
犹些多它：[答案] 不会...

准格尔旗17770811570： 数据结构试题4、已知待排序列以下,利用二路归并排序进行按小到大排序,除了最终结果外,要求写出每一趟排序的结果.初始序列为:[8] [4] [5] [6] [2] [1] [7] ... - ？
犹些多它：[答案] 1、 4 8 5 6 1 2 3 7 2、 4 5 6 8 1 2 3 7 3、 1 2 3 4 5 6 7 8

准格尔旗17770811570： 数据结构考题1、在双向循环链表的p所指结点之后插入s所指结点的操作是().Ap - >right=s;s - >left=p;p - >right - >left=s;s - >right=p - >right;Bp - >right=s;p - >right - >left... - ？
犹些多它：[答案] 答案保证正确,1、在双向循环链表的p所指结点之后插入s所指结点的操作是(D).Ap->right=s;s->left=p;p->right->left=s;s->right=p->right;Bp->right=s;p->right->left=s;s->left=p;s->right=p->right;Cs->left=p;s->...

准格尔旗17770811570： 数据结构的试题求帮忙1.在( )链表中,从任何一结点出发都能访问到表中的所有结点.2.栈和队列均是运算受限的线性表,栈的特点是(),队列的特点... - ？
犹些多它：[答案] 循环先进后出,先进先出递增序列数据元素 数据项36 38 40 40 46 56 79 80 24 66 75 84顺序串 链接串一 无 至少一front=rear (rear+1)%Queuelen=rear rear-front rear-front+Queuelen层次5 169

准格尔旗17770811570： 数据结构试题设一棵三叉树中有50个度数为0的结点,21个度数为2的结点,则该二叉树中度数为3的结点数有______个. 写上过程 谢谢 - ？
犹些多它：[答案] 答案是 度数为3的结点有14个. 假设: 三叉树中度为3的结点x个,度为2的结点y个,度为1的结点z个,度为0的结点m个,总结点数sum sum = x+y+z+m 从另外一个角度看,除了根节点,树的每个结点上方都关联一个分支, 所以总结点数sum=分支数+...

准格尔旗17770811570： 数据结构高手进,安徽电大数据结构期末试题一一、单选题(每小题3分,共30分)1、对于单链表形式的队列,队空的条件是( )A、F=R=NULL B、 F=R ... - ？
犹些多它：[答案] 一、 1、B 2、B 4、C 《 A的深度为1,B的深度为3,D的深度为3》 5、C 6、B? 7、C 8、B 直接插入排序 :n个不同的数据元素,最多需要比较n*(n-1)/2 9、C 10、A 二、 1.线性结构 ,非线性结构 . 2.352 ,232 . 3.i能被2整除,i+1 4、log2(2n+1) ,2n-1 ...

准格尔旗17770811570： 数据结构练习题闲着.7. 在一棵二叉树中,度为0的结点个数为n0,度为2的结点个数为n2,则n0=______.8. 一棵深度为k的满二叉树的结点总数为_______,... - ？
犹些多它：[答案] 7.n2+1 8.2^k-1,2^(k-1),2^k-1 9.5 10 2h-1 1.2 2.n(n-1)/2 ,n(n-1) 3.2,4 4 .n-1 5.邻接矩阵和邻接表

准格尔旗17770811570： 求下面数据结构试题的答案...谢谢...1.算法的计算量大小称为计算的( )2.从逻辑上,可以把数据结构分为( )两大类.3.下述哪一条是顺序存储结构的优点... - ？
犹些多它：[答案] 1效率;2非结构,结构;3;4数据元素;5后进先出;6n;7Q.front->next=Q.front->next->next;9.1,2 ; 10 -+A*BC/DE11 子结点 12 ;13 n(n-1)/2; 14 n-1 ;15 2n-1;17 顺序存储表示 19 表最后一个结...

准格尔旗17770811570： 数据结构习题计算储存地址假设按低下标优先存储整数数组A9*3*5*8时,第一个元素的字节地址是 100,每个整数占四个字节.问下列元素的存储地址是什么... - ？
犹些多它：[答案] 从第一个数字开始100+(3*3*5*8+1*5*8+2*8+5)*4=1784,这个是基本的啊