《数据结构(计算机科学与技术)》由会员分享，可在线阅读，更多相关《数据结构(计算机科学与技术)（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构(计算机科学与技术本科)第一部分 客观题一、单项选择(每题2分，共20 分)1、设 n 为正整数。则下面程序段的时间复杂度为。k=0;for(i=1;i=n;i+)for(j=i;jnext;q = head;while (p != NULL & p-data next;p = (ListNode *)malloc (sizeof(ListNode);p-data = x;p-next = q-next;q-next = p;2、假设将循环队列定义为：以整型域变量fro nt和len gth分别指示循环队列中队 头元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地
2、址，写出相应的入队列和出队列的算法。1.typedef char QElemType;2.typedef struct 3.4.int length;5.int rear;6.CLenQueue;7.Status EnCQueue(CLenQueue &Q, QElemType x)8.9.10.if(Q.length = MAXQSIZE)return ERROR;/循环队列满QElemType elemMAXQSIZE;12. if(MAXQSIZE - 1 != Q.rear)13. +Q.rear;14. Q.elemQ.rear=x;15. 16. else/rear指向循环队列的末
3、尾时，作特殊处理使其构成循环17. Q.rear = 0;18. Q.elemQ.rear=x;19. 20. +Q.leng th;/当前元素个 数+121. return OK;22. 23.23. Status DeCQueue(CLenQueue &Q, QElemType &x)24. 25. if(!Q.length)26. return ERROR;/循环队列空27. 28. if(Q.rear + 1 = Q.length)/当rear的下标大于对头指向的下标时29. x = Q.elemQ.rear + 1 - Q.length;30. 31. else/当rear的下标小于
4、队头下标时32. x = Q.elemMAXQSIZE + Q.rear + 1 - Q.length;33. 34. -Q.leng th;/当前元素个数-135. return OK;36. 37. #include 38. #include 39. #define QUEUE_SIZE 1040. /*循环队列结构体*/41. typedef struct 42. int front; /* 队列头 */43. int rear; /* 队列尾 */44. int length; /*记录队列元素个数*/45. int dataQUEUE_SIZE; /*存放队列元素值的数组*/46.
5、CirQueue;47. /*初始化队列*/48. void initQueue(CirQueue *Q)49. 50. Q-front = Q-rear = 0;51. Q-length = 0;52. 53. /*判断队列是否为空*/54. int QueueEmpty(CirQueue *Q)55. 56. return Q-length = 0;57. 58. /*判断队列满*/59. int QueueFull(CirQueue *Q)60. 61. return Q-length = QUEUE_SIZE;62. 63. /*入队列*/64. void EnQueue(CirQue
6、ue *Q, int data)65. 66. if (QueueFull(Q)67. printf(队列已经满 了.n);68. Q-length + +; /*队列元素个数加1 */69. Q-dataQ-rear = data; /* 将新元素插入队尾 */70. Q-rear = (Q-rear+1)%QUEUE_SIZE; /* 将队尾加 1 */71. 72. /*出队列*/73. int Dequeue(CirQueue *Q)74. 75. int temp;76. if (QueueEmpty(Q)77. printf(队列已经为空!n);78. temp = Q-dataQ-front;79. Q-length-; /*队列元素个数减1 */80. Q-front = (Q-front+1)%QUEUE_SIZE; /* 队列头加 1 */81. return temp;82. 83. /*测试程序*/84. int main()85. 86. CirQueue Q;87. int input = 0; /*入队数据，由用户输入*/88. /*初始化队列*/89. initQueue(&Q);9L prinm鸯92孟斋93. whi-e(一QueueFU-(siQ)94宀95 scanf(=%d
